Search   Memberlist   Usergroups
 Page 1 of 16 [234 Posts] View previous topic :: View next topic Goto page:  1, 2, 3, ..., 14, 15, 16 Next
Author Message
Anton Deitmar
science forum beginner

Joined: 25 Jul 2005
Posts: 24

Posted: Thu Jul 20, 2006 2:00 pm    Post subject: Re: A Combinatorics/Graph Theory Question

It seems to me that p equals C(n-1,k)+r.
The number of elements of Y to which a given x in X is not connected,
equals the number of k-element subsets of X which do not contain x,
that is C(n-1,k). Hence, to make sure you pick at least r sets which do
contain x, you must pick C(n-1,k)+r sets.

Did I miss anything?
Anton
Philippe Flajolet
science forum beginner

Joined: 18 Jun 2006
Posts: 1

Posted: Sun Jun 18, 2006 10:45 am    Post subject: Re: Refree's query

 Quote: I am considering differential equations of the form: y'*x*(1+y*(d/dz){log(F_{k}(z)}_{z=y})=y

I hope I interpret the statement correctly, though I don't see the exact meaning of "IDENTICALLY complex functions" in the original specification. Also, the z,y notation business seems to me to be a bit obscuring the simplicity of the problem.

Instead of a very specific F_k, subsitute an arbitrary function F(y). Then the differential equation reads

y'*x(1+y*F'(y)/F(y))=y

that is,

y'/y+F'(y)/F(y)=1/x,

which integrates to give

log(y)+log(F(y))=log(x), that is, y*F(y)=x.

Thus, a generalized form of the original equation is plainly solved via inversion of an explicit function, no matter what the structure of F is. This is a type of equation encountered when analysing the Lambert function (y*exp(y)=x) and, in the variant form y=x*G(y), is related to tree enumerations in combinatorial analysis as well as to Lagrange inversion.

On an another register, the particular class of functions F_k that you introduce seem to be composed of some sort of "towers of exponentials": depending on the way you specify F_0, they might be described as the class of functions defined as corresponding to terms expressed using the variable "z" [or better "y"?], the unary construction exp(.), the binary operation "*", and perhaps "+" and/or some other operations. There has been quite a bit of research in mathematical logic for deciding equality or dominance of functions of this sort [eg, exp(2*y)=exp(y)*exp(y), etc]. A starting point to this literature might be

Some Application of Nevanlinna Theory to Mathematical Logic: Identities
Exponential Functions. C. Ward Henson, Lee A. Rubel
Transactions of the American Mathematical Society, Vol. 282, No. 1
(Mar., 1984) , pp. 1-32

and references therein.

Philippe
Swiatoslaw Gal
science forum beginner

Joined: 02 Jun 2006
Posts: 1

Posted: Fri Jun 02, 2006 12:38 pm    Post subject: Re: This Week's Finds in Mathematical Physics (Week 233)

 Quote: f: SL(2,R)/SL(2,Z) -> R^3 - {trefoil} That would be amazing really- because then we could compose with modular forms and maybe obtain something interesting! I would also definitely like the answer to this.

Not realy.
In fact the isomorphism is a part of the modular theory:

Looking for

f: Gl(2,R)/Sl(2,Z)\to C^2-{x^2=y^3}

(there is an obvious action of R_+ on both sides:
M\to tM (M\in Gl(2,R) , x\to t^6 x, y\to t^4 y,
and that the quotient is what we want).

Gl(2,R)/Sl(2,Z) is a space of lattices in C.
Such a lattice L has classical invariants
g_2(L) = 60 \sum_{z\in L'} z^{-4}, and
g_3(L) = 140 \sum_{z\in L'} z^{-6},
where L'=L-{0}

The modular theory asserts that
1. For every pain (g_2,g_3) there exist a lattice L,
such that g_2(L)=g_2, and g_3(L)=g_3 provided
(g_2/3)^2\neq g_3.
2. Such a lattice is unique.

Best,
S. R. Gal
Joe Christy
science forum beginner

Joined: 01 Jun 2006
Posts: 2

Posted: Thu Jun 01, 2006 3:00 pm    Post subject: Re: This Week's Finds in Mathematical Physics (Week 233)

Vis-a-vis John's note of 05/30/2006 03:06 PM:
 Quote: In article <1148262406.418804.233710@i39g2000cwa.googlegroups.com>, Daniel Moskovich wrote: And, R^3 minus the trefoil knot is secretly the same as SL(2,R)/SL(2,Z)! This is actually incredibly interesting for me- what is a reference for this? (I couldn't find it in either cited paper, and Gannon gives no source). As usual, I gave all the references I know. I too find this fact incredibly interesting. I first heard of it from Chris Hillman: http://www.lns.cornell.edu/spr/2002-04/msg0040885.html ...

I wouldn't be surprised if this was known to Seifert in the 30's,
though I can't lay my hands on Seifert & Threfall at the moment to
check. Likewise for Hirzebruch, Brieskorn, Pham & Milnor in the 60's in
relation to singularities of complex hypersurfaces and exotic spheres.
When I was learning topology in the 80's it was considered a warm up
case of Thurston's Geometrization Program - the trefoil knot complement
has PSL_2(R) geometric structure.

In any case, peruse Milnor's Annals of Math Studies for concrete
references. There is a (typically) elegant proof on p.84 of
"Introduction to Algebraic K-theory" [study 72], which Milnor credits to
to Quillen. It contains the missing piece of John's argument:
introducing the Weierstrass P-function and remarking that the
differential equation that it satisfies gives the diffeomorphism to
S^3-trefoil as the boundary of the pair (discriminant of diff-eq, C^2 =
(P,P')-space).
This point of view grows out of some observations of Zariski, fleshed
out in "Singular Points of Complex Hypersurfaces" [study 61]. The
geometric viewpoint is made explicit in the paper "On the Brieskorn
Manifolds M(p,q,r)" in "Knots, Groups, and 3-manifolds" [study 84].

It is also related to the intermediate case between the classical
Platonic solids and John's favorite Platonic surface - the Klein quartic
http://www.math.ucr.edu/home/baez/klein.html. By way of a hint, look to
relate the trefoil, qua torus knot, the seven-vertex triangulation of
the torus, and the dual hexagonal tiling of a (flat) Clifford torus in S^3.

Joe

--
============================= Joe Christy ==============================
------------------ http://xri.net/=joe.christy ------------------
== If I can save you any time, give it to me, I'll keep it with mine. ==
Joe Christy
science forum beginner

Joined: 01 Jun 2006
Posts: 2

Posted: Thu Jun 01, 2006 6:07 am    Post subject: Re: This Week's Finds in Mathematical Physics (Week 233)

Vis-a-vis John's note of 05/30/2006 03:06 PM:
 Quote: In article <1148262406.418804.233710@i39g2000cwa.googlegroups.com>, Daniel Moskovich wrote: And, R^3 minus the trefoil knot is secretly the same as SL(2,R)/SL(2,Z)! This is actually incredibly interesting for me- what is a reference for this? (I couldn't find it in either cited paper, and Gannon gives no source). As usual, I gave all the references I know. I too find this fact incredibly interesting. I first heard of it from Chris Hillman: http://www.lns.cornell.edu/spr/2002-04/msg0040885.html ...

I wouldn't be surprised if this was known to Seifert in the 30's,
though I can't lay my hands on Seifert & Threfall at the moment to
check. Likewise for Hirzebruch, Brieskorn, Pham & Milnor in the 60's in
relation to singularities of complex hypersurfaces and exotic spheres.
When I was learning topology in the 80's it was considered a warm up
case of Thurston's Geometrization Program - the trefoil knot complement
has PSL_2(R) geometric structure.

In any case, peruse Milnor's Annals of Math Studies for concrete
references. There is a (typically) elegant proof on p.84 of
"Introduction to Algebraic K-theory" [study 72], which Milnor credits to
to Quillen. It contains the missing piece of John's argument:
introducing the Weierstrass P-function and remarking that the
differential equation that it satisfies gives the diffeomorphism to
S^3-trefoil as the boundary of the pair (discriminant of diff-eq, C^2 =
(P,P')-space).
This point of view grows out of some observations of Zariski, fleshed
out in "Singular Points of Complex Hypersurfaces" [study 61]. The
geometric viewpoint is made explicit in the paper "On the Brieskorn
Manifolds M(p,q,r)" in "Knots, Groups, and 3-manifolds" [study 84].

It is also related to the intermediate case between the classical
Platonic solids and John's favorite Platonic surface - the Klein quartic
http://www.math.ucr.edu/home/baez/klein.html. By way of a hint, look to
relate the trefoil, qua torus knot, the seven-vertex triangulation of
the torus, and the dual hexagonal tiling of a (flat) Clifford torus in S^3.

Joe

--
============================= Joe Christy ==============================
------------------ http://xri.net/=joe.christy ------------------
== If I can save you any time, give it to me, I'll keep it with mine. ==
Bruce Ikenaga
science forum beginner

Joined: 04 Nov 2005
Posts: 3

Posted: Thu Jun 01, 2006 6:05 am    Post subject: Re: This Week's Finds in Mathematical Physics (Week 233)

On Tue, 30 May 2006 22:06:24 +0000, John Baez wrote:

 Quote: In article <1148262406.418804.233710@i39g2000cwa.googlegroups.com>, Daniel Moskovich wrote: And, R^3 minus the trefoil knot is secretly the same as SL(2,R)/SL(2,Z)! This is actually incredibly interesting for me- what is a reference for this? (I couldn't find it in either cited paper, and Gannon gives no source). As usual, I gave all the references I know. I too find this fact incredibly interesting. I first heard of it from Chris Hillman: http://www.lns.cornell.edu/spr/2002-04/msg0040885.html I feel I can *almost* prove it, but not quite. SL(2,R)/SL(2,Z) is the space of unit-area lattices in the plane. If we take the hexagonal lattice * * * * * * * * * * * and gradually rotate it 60 degrees, we get back to the same lattice. So, we have traced out a certain loop A in SL(2,R)/SL(2,Z). If we take the square lattice: * * * * * * * * * * * * and rotate it 90 degrees, we get another loop B. I believe that these define elements of pi_1(SL(2,R)/SL(2,Z)) satisfying A^3 = B^2. This is the usual presentation for the fundamental group of the complement of the trefoil knot: http://en.wikipedia.org/wiki/Trefoil_knot I think the loop A corresponds to going around a "meridian" and B corresponds to going around a "longitude" - or maybe vice versa, since I can never remember the difference between the "meridian" and the "longitude" of a knot. But, there should be some more direct way to see what's going on! Since the Wikipedia article gives an analytic formula for the trefoil knot, maybe someone come up with an analytic formula for a diffeomorphism f: SL(2,R)/SL(2,Z) -> R^3 - {trefoil} Help, anyone?

Quillen's proof is on pages 84-85 of Milnor's "Introduction to
Algebraic K-Theory".

Bruce Ikenaga
John Baez
science forum Guru Wannabe

Joined: 01 May 2005
Posts: 220

Posted: Tue May 30, 2006 10:06 pm    Post subject: Re: This Week's Finds in Mathematical Physics (Week 233)

Daniel Moskovich <dmoskovich@gmail.com> wrote:

 Quote: And, R^3 minus the trefoil knot is secretly the same as SL(2,R)/SL(2,Z)! This is actually incredibly interesting for me- what is a reference for this? (I couldn't find it in either cited paper, and Gannon gives no source).

As usual, I gave all the references I know. I too find this fact
incredibly interesting. I first heard of it from Chris Hillman:

http://www.lns.cornell.edu/spr/2002-04/msg0040885.html

I feel I can *almost* prove it, but not quite.

SL(2,R)/SL(2,Z) is the space of unit-area lattices in the plane.
If we take the hexagonal lattice

* * * *

* * *

* * * *

and gradually rotate it 60 degrees, we get back to the
same lattice. So, we have traced out a certain loop A in
SL(2,R)/SL(2,Z). If we take the square lattice:

* * * *

* * * *

* * * *

and rotate it 90 degrees, we get another loop B.

I believe that these define elements of pi_1(SL(2,R)/SL(2,Z))
satisfying A^3 = B^2. This is the usual presentation for the
fundamental group of the complement of the trefoil knot:

http://en.wikipedia.org/wiki/Trefoil_knot

I think the loop A corresponds to going around a "meridian"
and B corresponds to going around a "longitude" - or maybe
vice versa, since I can never remember the difference between
the "meridian" and the "longitude" of a knot.

But, there should be some more direct way to see what's going on!

Since the Wikipedia article gives an analytic formula for the
trefoil knot, maybe someone come up with an analytic formula
for a diffeomorphism

f: SL(2,R)/SL(2,Z) -> R^3 - {trefoil}

Help, anyone?
Matt Heath
science forum beginner

Joined: 04 Apr 2006
Posts: 3

Posted: Fri May 05, 2006 2:21 pm    Post subject: Re: Absolutely continuous functions on the circle and disc algebra function

You are quite right. A false argument lead me to think it was the same as case with f anti-analytic, which is really what I am trying to solve.
Bernice Barnett
science forum beginner

Joined: 08 May 2005
Posts: 5

Posted: Wed Apr 12, 2006 12:30 pm    Post subject: Re: A conditional random number generation problem (please help me!)

Giovanni Resta wrote:
 Quote: rjmachado3 wrote: I need to know the formula for the random function that return random numbers in a range of a and b integers [a,b] but that obey on a custom probability (possibly different!) for each integer number on this [a,b] range (of course the sum of all integer number probabilities are = 1!). Finally, what i want is the general function formula that simulate the random behavior (based on a custom probability value for each integer number between the [a,b] range. confuse? i hope not! please help me!!!! what i know so far is that the function formula for generating a "pure" random number between [a,b] range is: rand()*(b-a)+a where rand() return a random number between 0 and 1. I'm not completely sure to have correctly understood you question. Anyway... Here is a very naive apprach that can work, at least if the interval is small. Maybe if the interval is large one can think about something more efficient. I make an example with 4 values, each with a custom prob., that can be easily generalized. Let the integer values be a,b,c,d (they do not need to be consecutive numbers) and let p_a, p_b, p_c, p_d the probability to extract respectively a,b,c, and d. Clearly p_a+p_b+p_c+p_d = 1. First you build these constants: P_a = p_a P_b = p_a+p_b P_c = p_a+p_b+p_c then you extract a random number U between 0 and 1, and if U <= P_a you select a, else if U <= P_b you select b else if U <= P_c you select c else you select d. I hope this example helps you giovanni There is an improvement if the range is large: Make a table of the

distribution (your P_x above). Then generate a uniform random as above.
Finally, do a binary search on the table - complexity O(log(n)) where n
is the number of table entries. I think this is the best you can do for
distributions where you don't have an inverse of the distribution function.

-- Jeff Barnett
Giovanni Resta
science forum beginner

Joined: 11 Apr 2006
Posts: 1

Posted: Tue Apr 11, 2006 4:30 pm    Post subject: Re: A conditional random number generation problem (please help me!)

 Quote: I need to know the formula for the random function that return random numbers in a range of a and b integers [a,b] but that obey on a custom probability (possibly different!) for each integer number on this [a,b] range (of course the sum of all integer number probabilities are = 1!). Finally, what i want is the general function formula that simulate the random behavior (based on a custom probability value for each integer number between the [a,b] range. confuse? i hope not! please help me!!!! what i know so far is that the function formula for generating a "pure" random number between [a,b] range is: rand()*(b-a)+a where rand() return a random number between 0 and 1.

I'm not completely sure to have correctly understood you
question. Anyway...
Here is a very naive apprach that can work, at least
if the interval is small. Maybe if the interval is large
one can think about something more efficient.

I make an example with 4 values, each with a custom prob.,
that can be easily generalized.

Let the integer values be a,b,c,d (they do not need to be consecutive
numbers) and let p_a, p_b, p_c, p_d the probability to
extract respectively a,b,c, and d.
Clearly p_a+p_b+p_c+p_d = 1.

First you build these constants:

P_a = p_a
P_b = p_a+p_b
P_c = p_a+p_b+p_c

then you extract a random number U between 0 and 1, and

if U <= P_a you select a,
else if U <= P_b you select b
else if U <= P_c you select c
else you select d.

I hope this example helps you
giovanni
Matt Heath
science forum beginner

Joined: 04 Apr 2006
Posts: 3

 Posted: Tue Apr 04, 2006 4:57 pm    Post subject: Re: Results for: 'From Commutative Algebra to Functional Analysis' For semi-simple algebras there is a theorem of Johnson that a Banach algebra norm is unique - and hence that being a semi-simple Banach algebra is an algebraic property.
DariushA
science forum beginner

Joined: 15 Mar 2006
Posts: 5

Posted: Sat Mar 18, 2006 11:15 am    Post subject: Re: Subset Vector Sum

I think the algorithms Victor directed me to will keep me
happily busy for a while.

I will report any possible progress.

Much Regards,

Dariush.

"Victor S. Miller" <victor@algebraic.org> wrote in message
news:dveofd$2s6$1@dizzy.math.ohio-state.edu...
 Quote: "Gerhard" == Woeginger Gerhard This is a 2-dimensional variant of SUBSET-SUM (Given n Gerhard> integers a_1,...,a_n and a goal-value b, does there exists a Gerhard> subset of the a_i that adds up to b?). Gerhard> SUBSET-SUM is NP-hard. The special case of SUBSET-SUM with Gerhard> b=0 is also NP-hard. Gerhard> So you should not expect a fast solution algorithm for your Gerhard> 2-dimensional generalization. On the contrary -- just because the general problem is NP complete doesn't mean that your specific instance might not be solved quickly. This is a special case of the integer relation algorithm. For example, look at the following page for a good overview. The Ferguson-Forcade, or PSLQ algorithm might be a good one to use. You can also set this up for lattice reduction and use the LLL algorithm. Victor http://mathworld.wolfram.com/IntegerRelation.html
tchow@lsa.umich.edu

Joined: 15 Sep 2005
Posts: 53

Posted: Tue Feb 14, 2006 1:18 am    Post subject: Re: This Week's Finds in Mathematical Physics (Week 226)

In article <dsn2cd$som$1@glue.ucr.edu>, John Baez <baez@galaxy.ucr.edu> wrote:
 Quote: Alexander A. Razborov and Steven Rudich, Natural proofs, in Journal of Computer and System Sciences, Vol. 55, No 1, 1997, pages 24-35. Available at http://www-2.cs.cmu.edu/~rudich/papers/natural.ps and http://genesis.mi.ras.ru/~razborov/int.ps Aaronson says it was written in 1993 even though the date of publication and the date on the paper itself (1996 or 1999, depending on which copy you look at) are later. I believe him; you have to be careful when using the /today command in LaTeX, since if you LaTeX the same paper 6 years later, you'll get a new date.

It probably has less to do with the "today" command than with the fact
that papers in computer science tend to exist in more versions than in,
say, math. The two "official" versions of the Razborov-Rudich paper are
STOC 1994 (conference version) and JCCS 1997 (journal version). However,
I wouldn't be surprised if it circulated in preprint form in 1993, and if
the authors continued to revise the paper after the "final" journal version,
since this isn't uncommon practice.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
baez@galaxy.ucr.edu

Joined: 21 Oct 2005
Posts: 53

Posted: Mon Feb 13, 2006 8:08 pm    Post subject: Re: This Week's Finds in Mathematical Physics (Week 226)

In article <Pine.LNX.4.61.0602102025360.19201@zeno1.math.washington.edu>,
<tessel@um.bot> wrote:

 Quote: On Sat, 11 Feb 2006, John Baez mentioned that md5sum was "broken" about a year ago. I just wanted to add: 1. If I am not mistaken, sha-1 and md5sum are different algorithms (IIRC, both are known to be insecure).

Yeah. Here's a nice review of the situation:

Arjen K. Lenstra, Further progress in hashing cryptanalysis,
February 26, 2005, http://cm.bell-labs.com/who/akl/hash.pdf

 Quote: These are huge and wonderful philosophico-physico-mathematical questions with serious practical implications. You mean the Weyl curvature hypothesis? :-/

Heh, no - I mean stuff like whether there's such a thing as a provably
good cryptographic hash code function, or cipher.

 Quote: Joel Spencer, The Strange Logic of Random Graphs, Springer 2001 Here's a thought: "Everyone knows" that if on day D, mathematician M is studying an example of size S in class C, he is more likely to be studying a "secretly special" representative R than a generic representative G of size S. Why? Because the secretly special reps show up in disguise in other areas, and M was probably hacking through the jungle from one of those places when he got lost and ate a poisoned cache.

Interesting.

Here's some more stuff, from my email correspondence.

I wrote:

 Quote: Allan Erskine wrote: I enjoyed week 226! Algorithmic complexity was the area I studied in... Your readers might find "The Tale of One-way Functions" by Leonid Levin an enjoyable read: http://arxiv.org/abs/cs.CR/0012023 Hey, that's great! I'm printing it out now... Levin and I have argued against Greg Kuperberg and others on sci.physics.research: we tend to think that quantum computers are infeasible *in principle*. As for your "shortest proof of this statement has n lines" question, you may have noticed that Chaitin asks a very similar question about the shortest proofs that a LISP program is "elegant" (most short) and proves a strong incompleteness result with an actual 410 + n character LISP program! Crazy... http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.html Yes. You might like the following related article below. Best, jb

It's an old one...

From: b...@math.ucr.edu (john baez)
Subject: Re: compression, complexity, and the universe
Date: 1997/11/20
Message-ID: <652c5t$62g$1@agate.berkeley.edu>#1/1
X-Deja-AN: 291100089
References: <64nsqo$8rg$1@agate.berkeley.edu> <346fd86d.1059260@news.demon.co.uk> <64t2ar$qcs@charity.ucr.edu> Originator: bunn@pac2 Organization: University of California, Riverside Newsgroups: sci.physics.research,comp.compression.research In article <651lm1$q3...@agate.berkeley.edu>,
Aaron Bergman <aaron.berg...@yale.edu> wrote:

 Quote: The smallest number not expressable in under ten words

Hah! This, by the way, is the key to that puzzle I laid out:
prove that there's a constant K such that no bitstring can be
proved to have algorithmic entropy greater than K.

I won't give away the answer to the puzzle; anyone who gets
stuck can find the answer in Peter Gacs' nice survey, "Lecture
notes on descriptional complexity and randomness", available at

http://www.cs.bu.edu/faculty/gacs/

In my more rhapsodic moments, I like to think of K as the
"complexity barrier". The world *seems* to be full of incredibly
complicated structures --- but the constant K sets a limit on our
ability to *prove* this. Given any string of bits, we can't rule
out the possibility that there's some clever way of printing it
out using a computer program less than K bits long. The Encyclopedia
Brittanica, the human genome, the detailed atom-by-atom recipe for
constructing a blue whale, or for that matter the entire solar system
--- we are unable to prove that a computer program less than K bits
long couldn't print these out. So we can't firmly rule out the
reductionistic dream that the whole universe evolved mechanistically
starting from a small "seed", a bitstring less than K bits long.
(Maybe it did!)

So this raises the question, how big is K?

It depends on ones axioms for mathematics.

Recall that the algorithmic entropy of a bitstring is defined
as the length of the shortest program that prints it out. For
any finite consistent first-order axiom system A exending the
usual axioms of arithmetic, let K(A) be the constant such that
no bitstring can be proved, using A, to have algorithmic entropy
greater than K(A). We can't compute K(A) exactly, but there's a
simple upper bound for it. As Gacs explains, for some constant c
we have:

K(A) < L(A) + 2 log_2 L(A) + c

where L(A) denotes the length of the axiom system A, encoded as
bits as efficiently as possible. I believe the constant c is
computable, though of course it depends on details like what
universal Turing machine you're using as your computer.

What I want to know is, how big in practice is this upper
bound on K(A)? I think it's not very big! The main problem
is to work out a bound on c.
baez@galaxy.ucr.edu

Joined: 21 Oct 2005
Posts: 53

Posted: Sun Feb 12, 2006 9:59 pm    Post subject: Re: This Week's Finds in Mathematical Physics (Week 226)

Here are some corrections and clarifications, mostly thanks to a
friend who usually prefers to remain anonymous:

In article <dsirq1$pjg$1@glue.ucr.edu>,
John Baez <baez@math.removethis.ucr.andthis.edu> wrote:

 Quote: MD5 is a popular hash function invented by Ron Rivest in 1991.

This is what it says in Wikipedia:

http://en.wikipedia.org/wiki/MD5

with a big picture of Rivest right on top of the article,
but my friend says

"I think it's usually credited to a small set of coinventors,
and I think Ralph Merkle is a coinventor either of MD5 or one
of its immediate ancestors."

 Quote: People use it for checking the integrity of files: first you compute the digest of a file, and then, when you send the file to someone, you also send the digest. If they're worried that the file has been corrupted or tampered with, they compute its digest and compare it to what you sent them.

Of course, if deliberate tampering is what you fear, you have
to send the digest by a different channel than the original file,
or use some other trick.

 Quote: But if you prove that P *does* equal NP, you might make more money by breaking cryptographic hash codes and setting yourself up as the Napoleon of crime.

Or, you could make lots of money by solving problems that nobody
else can solve. This could be a more sustainable lifestyle... but
I wanted to work in a reference to that Sherlock Holmes quote, to
play off against the von Neumann quote.

 Quote: We can define a "random sequence" to be one that no algorithm can guess with a success rate better than chance would dictate.

Here "generate" would be clearer than "guess", since I was
trying to allude to the usual notion of randomness from
algorithmic information theory (in an informal sort of way).

I don't know if there are sequences that no algorithm can generate
with a success rate beating chance, but where an algorithm can do
well guessing the (n+1)st digit after having seen the first n.
Does anyone know?

 Quote: Chaitin has given a marvelous definition of a particular random sequence of bits called Omega using the fact that no algorithm can decide which Turing machines halt... but this random sequence is uncomputable, so you can't really "exhibit" it:

On the other hand, Wolfgang Brand points out this paper:

http://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf

where the first 64 bits of Omega have been computed.

(There's no contradiction, as the paper explains.)

 Quote: Then Aaronson gets to the heart of the subject: a history of the P vs. NP question. This leads up to the amazing 1993 paper of Razborov and Rudich, which I'll now summarize.

Here's the paper:

Alexander A. Razborov and Steven Rudich, Natural proofs, in
Journal of Computer and System Sciences, Vol. 55, No 1, 1997, pages 24-35.
Available at http://www-2.cs.cmu.edu/~rudich/papers/natural.ps and
http://genesis.mi.ras.ru/~razborov/int.ps

Aaronson says it was written in 1993 even though the date of publication
and the date on the paper itself (1996 or 1999, depending on which copy
you look at) are later. I believe him; you have to be careful when using
the /today command in LaTeX, since if you LaTeX the same paper 6 years
later, you'll get a new date.

 Quote: The P versus NP question can be formulated as a question about the size of Boolean circuits - but Razborov and Rudich show that, under certain assumptions, there is no "natural" proof that P is not equal to NP. What are these assumptions? They concern the existence of good pseudorandom number generators. However, the existence of these pseudorandom number generators would follow from P = NP! So, if P = NP is true, it has no natural proof.

Aargh!

In both cases here when I wrote P = NP, I meant P *not* equal to NP.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 16 [234 Posts] Goto page:  1, 2, 3, ..., 14, 15, 16 Next View previous topic :: View next topic
 The time now is Mon Aug 20, 2018 3:47 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics WHEW! The Real Cause of Global Warming Ed Conrad Chem 0 Wed Jul 19, 2006 1:24 pm Why you can not count real number? cyclomethane@gmail.com Math 13 Mon Jul 10, 2006 11:59 am Real Integral w/ Complex Analysis Narcoleptic Insomniac Math 8 Sat Jul 08, 2006 1:16 pm function semi-algebraic over real closed sub-field? Martin Ziegler Research 0 Sat Jul 08, 2006 8:17 am Signal Nonlocality Real or Imaginary? Jack Sarfatti Math 0 Sat Jul 08, 2006 4:33 am