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@xxxxxxxxxxxx>,
John Baez <baez@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

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."

I'd like more information on this.

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.

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.

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).

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.)

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.

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.



.

Relevant Pages

  • Re: This Weeks Finds in Mathematical Physics (Week 226)
    ... friend who usually prefers to remain anonymous: ... digest of a file, and then, when you send the file to someone, you also send ... I don't know if there are sequences that no algorithm can generate ... Alexander A. Razborov and Steven Rudich, Natural proofs, in ...
    (sci.math.research)
  • Re: Airplanes and Brakes?
    ... "A Little Help From A Friend" Dudley Henriques,Reader's Digest April ... To much godbothering and 'prize' hooks for the unwary and gullible. ...
    (rec.aviation.piloting)
  • Re: Am I Calling it Quits? Well Some Day Soon, I Think.
    ... write if you need help moderating the digest or with other chores. ... Then a couple days ago, the Friend ... Please don't hesitate to ask if you need help with the digest or other ...
    (comp.dcom.telecom)