Zeilberger on why P differs from NP
Scott Aaronson, Lance Fortnow and Bill Gasarch have discussed the reasons why they believe P differs from NP here, here and here.
Doron Zeilberger, motivated by Avi Wigderson's talk in Madrid devotes his latest opinion to the subject. (Via Luca A.)
His dismissal of the creativity cannot be mechanized argument is based on his long-standing belief (which I share) that human creativity, especially human mathematical creativity can in fact be emulated by algorithms and that, in the long run, algorithms will end up being superior. I think this is a misunderstanding of the argument, whose point is rather that creating something good (by humans and by algorithms) seems to require much more effort than appreciating something good, and that there are levels of "genius" which we would be able to recognize if we saw them but that we are prepared to consider infeasible. In the end, this is the same as the a fool can ask more questions than a wise man can answer argument that Zeilberger himself proposes.
Then there is the issue of whether it is fair to say that "P $\neq$ NP is a statement that affirms its own intractability." Indeed, the P versus NP question is a statement about asymptotics, while proving it is a problem of finite size.
I have two observations.
One is that the "natural proofs" results show that, assuming strong one-way functions exist (an assumption in the "ballpark" of P $\neq$ NP) there are boolean functions that are efficiently computable but have all the efficiently computable properties of random functions. This means that any circuit lower bound proof must work in a way that either would fail when applied to random functions (and there are reasons why it is difficult to come up with such proofs) or would rely on hard-to-compute properties of the function in question. So although the proof is a finite object, it does define an "algorithm" (the one that describes the properties of the function that are used in the proof) and such algorithm cannot be asymptotically efficient.
The other is that, however cleaner our theories are when formulated asymptotically, we should not lose sight of the fact that the ultimate goals of complexity theory are finite results. It will be a historic milestone when we prove that P $\neq$ NP by showing that SAT requires time at least $2^{-300} \cdot n^{(\log n) / 100 }$, but the real deal is to show that there is no circuit of size less than $2^{300}$ that solves SAT on all formulae having 10,000 clauses or fewer. The statements that we care about are indeed finite.
Doron Zeilberger, motivated by Avi Wigderson's talk in Madrid devotes his latest opinion to the subject. (Via Luca A.)
His dismissal of the creativity cannot be mechanized argument is based on his long-standing belief (which I share) that human creativity, especially human mathematical creativity can in fact be emulated by algorithms and that, in the long run, algorithms will end up being superior. I think this is a misunderstanding of the argument, whose point is rather that creating something good (by humans and by algorithms) seems to require much more effort than appreciating something good, and that there are levels of "genius" which we would be able to recognize if we saw them but that we are prepared to consider infeasible. In the end, this is the same as the a fool can ask more questions than a wise man can answer argument that Zeilberger himself proposes.
Then there is the issue of whether it is fair to say that "P $\neq$ NP is a statement that affirms its own intractability." Indeed, the P versus NP question is a statement about asymptotics, while proving it is a problem of finite size.
I have two observations.
One is that the "natural proofs" results show that, assuming strong one-way functions exist (an assumption in the "ballpark" of P $\neq$ NP) there are boolean functions that are efficiently computable but have all the efficiently computable properties of random functions. This means that any circuit lower bound proof must work in a way that either would fail when applied to random functions (and there are reasons why it is difficult to come up with such proofs) or would rely on hard-to-compute properties of the function in question. So although the proof is a finite object, it does define an "algorithm" (the one that describes the properties of the function that are used in the proof) and such algorithm cannot be asymptotically efficient.
The other is that, however cleaner our theories are when formulated asymptotically, we should not lose sight of the fact that the ultimate goals of complexity theory are finite results. It will be a historic milestone when we prove that P $\neq$ NP by showing that SAT requires time at least $2^{-300} \cdot n^{(\log n) / 100 }$, but the real deal is to show that there is no circuit of size less than $2^{300}$ that solves SAT on all formulae having 10,000 clauses or fewer. The statements that we care about are indeed finite.
posted by Luca at 6:08 PM
7 Comments:
12/14/2006 08:28:00 PM
On the spot is Zeilberger's comment about Theoretical Computer Scientists not using computers. Many TCS people seem to almost want to avoid computers, thus (perhaps) trying to acquire some "mathematical" credibility.
12/15/2006 10:27:00 AM
those people who are drawn to the intellectual content of CS, but not drawn to hacking, are the people who become theoretical computer scientists in the first place!
There are numerous counterexamples to your thesis, starting with Knuth.
12/15/2006 10:53:00 AM
Theoretical computer scientists use computers just as much as anyone else does. No more, no less.
Newton had no more use for the universe than you or I do...
12/15/2006 03:56:00 PM
those people who are drawn to the intellectual content of CS, but not drawn to hacking
That presupposses that use of computers don't have any intellectual content, which is exactly what Zeilberger is highlighting.
12/15/2006 06:30:00 PM
those people who are drawn to the intellectual content of CS, but not drawn to hacking
no, it doesn't. actually, it presupposes that people drawn to hacking will not want to do TCS, which is ridiculous.
12/15/2006 07:01:00 PM
All I have to say on the subject of hacking and theoreticians is that this has never happened to me
12/17/2006 02:53:00 PM
Why is the assumption that one way functions exist in the same ballpark as P != NP?
P != NP seems like a near certainty, given the seemingly magical abilities we would have if P = NP, but why one way functions? In this case, it seems like the existence of one-way functions allows us to do magical things.
Is there any reason to believe that one way functions exist, except that there are several candidates that people have not figured out how to efficiently invert in the last 30 or so years?
(Scott, if you are reading this, maybe you could do for one-way functions what you did for P != NP on your blog).
Post a Comment
<< Home