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.

About these ads

9 thoughts on “Zeilberger on why P differs from NP

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

  2. My adviser, Umesh Vazirani, told me when I was a prospective student that “theoretical computer science is the last refuge for people who don’t want to use computers.” For some reason, this statement made an indelible impression on me.

    I don’t think we have to postulate that theoretical computer scientists are trying to emulate their mathematician cousins — there are plenty of simpler ways they could do so, like deleting all motivation from their papers. I’d instead advocate a simple “anthropic” explanation: 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!

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

  4. 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…

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

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

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

  8. Mmmphhhh…

    Do you believe there are hard-on-average NP problems? If so, you’re already 90% of the way there. Indeed, I think we might someday be able to prove that hard-on-average NP problems imply one-way functions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s