Archive for September 28th, 2009

A conversation about complexity lower bounds, continued

September 28, 2009

This is the second part of a dialogue in which three characters, :), 8) and :|, discuss issues connected with the P versus NP problem. There are now nine parts: if this number continues to increase at a faster rate than I post them, then I may have to increase the rate of posting.

The story so far: πŸ™‚ has put forward one or two ideas, and 8) has drawn attention to the work of Razborov and Rudich that places very serious constraints on what any proof that P\neNP could possibly look like. This makes precise an intuition that πŸ™‚ had been beginning to build up after several failed attempts to find such a proof. πŸ™‚ then enthusiastically discusses further possible applications of the basic idea of Razborov and Rudich (seemingly unaware that Razborov and Rudich themselves had had similar but much more precise thoughts of the kind), before retiring to think for a while about what a “non-natural” proof might look like.


πŸ™‚ Hi again.

8) Hello. Got anything for us today?

πŸ™‚ I’m not really sure. But I have had a few thoughts that I’d like to try out on you.

8) Fire away.

πŸ™‚ Well, the result of Razborov and Rudich tells us that if we want to define some notion of “structure” or “simplicity” that all functions of low complexity have and some function in NP does not have, then we have a choice. Either almost all functions must be simple, or it must not be possible to decide in polynomial time whether a function is simple. I have to say that I rebel against the first, so I’ve been trying to come up with properties that one might be able to prove something about, despite their not being in P. (more…)