A Panel On P vs. NP
A discussion on the famous problem
William Agnew is the chairperson of the Georgia Tech Theoretical Computer Science Club. He is, of course, an undergraduate at Tech with a multitude of interests—all related to computer science.
Today I want to report on a panel that we had the other night on the famous P vs. NP question.
The panel consisted of two local people, one semi-local person, and two remote people—the latter were virtually present thanks to Skype. The local people were Lance Fortnow and myself, and the semi-local one was Dylan McKay. He was present at the panel, and was an undergraduate a bit ago at Tech. He is now a graduate student working with Ryan Williams, who both are moving from Stanford to MIT. The last was the Scott Aaronson who is not only an expert on P vs. NP, but also all things related to quantum computation.
An excellent panel, which I was honored to be part of. We had a large audience of students, who were no doubt there because of the quality of the panelists: although—sandwiches, drinks, and brownies—may have had some effect. They listened and asked some really good questions—some of which we could even answer.
The panel, like many panels, was fun to be on; and hopefully was informative to the audience. I believe the one point that all on the panel agreed with is: we do not know very much about the nature of computation, and there remains many many interesting things to learn about algorithms. I like the way Ryan put it:
We are like cave men and women banging rocks together and trying to see what happens.
This is not an exact quote, but you get the point: we are in the dark about what computers can and cannot do.
I thought I would summarize the panel by listing just a few questions that were discussed.
- Are there approaches to lower bounds that are promising?
- What is the relationship of quantum computing and P vs. NP?
- Could P vs. NP be independent of set theory?
- What would P=NP mean if it was true?
- Why are SAT solvers able to solve many “real” problems?
Irony and Self-Defeat
Scott recently released a 121-page survey on P versus NP. He did not read all of it during the panel. In fact he did not read any of it. It is chock full of content—for instance, the story about the Traveling Salesman Problem and Extended Formulations is told in a long footnote. It was partly supported by NSSEFF, which is not a phonetic spelling of NSF but stands for the National Security Science and Engineering Faculty Fellowship, soon to be renamed for Vannevar Bush.
It takes the stand that . Over half of the non-bibliography pages are in the section 6 titled “Progress.” This is great and completely up to date—not only through Ryan’s circuit lower bounds but also last year’s rebuff to the simplest attack in Ketan Mulmuley’s Geometric Complexity Theory paradigm. It details the three major barriers—relativization, “Natural Proofs,” and “Algebrization”—right in the context of where they impeached progress.
The climax in sections 6.4 and 6.6 is what Scott calls “ironic complexity” and Mulmuley calls the “flip”: the principle that to prove a problem X is harder to compute than we know, one may need to prove that another problem Y is easier to compute than we know. This gets dicey when the problems X and Y flow together. For instance, a natural proof that the discrete logarithm is nonuniformly hard to compute makes it nonuniformly easier to compute. Hence such a proof cannot give any more than a “half-exponential” lower bound (see this for definition). Ryan’s result, which originally gave a “third-exponential” lower bound on circuits for NEXP, proves lower bounds on a exponential scaling of SAT via upper bounds on an -like version; the two are brought a little closer by the former needing only succinct instances. Scott’s survey also emphasizes the fine line between “in-P” and “NP-hard” within cases of computational problems, arguing that if P=NP then we’d have found these lines fuzzed up long ago.
For my part—Ken writing this section—I’ve experienced a phenomenon that calls to mind our old post on “self-defeating sentences.” To evade the natural-proofs barriers, I’ve tried to base hardness predicates on problems that are hard for exponential space in terms of the number of variables in . The idea is to prove that circuits computing need size where is a counting function that scales with the complexity of , in analogy to the Baur-Strassen bounds where is the “geometric degree” of a variety associated to .
The Baur-Strassen tops out at when is a polynomial of degree , and since the low-degree polynomials we care about have , this accounts for why the best known arithmetical circuit lower bounds for natural functions are only . But extending the Baur-Strassen mechanism to double-exponentially growing would yield the exponential lower bounds we strive for. Candidates with names like “arithmetical degree” and (Castelnuovo-Mumford-)“regularity” abound, giving double-exponential growth and -hardness, but the latter sows the self-defeat: The hardness means there is a reduction to from length- instances of problems but the shortness of can make fail. I’ve described a based on counting “minimal monomials” in an ideal associated to , which although not necessarily complete still met the same defeat.
So maybe the constructive fact behind a problem’s NP-completeness also embodies a mirror image of a problem in P, so that we cannot easily tell them apart. NP-complete problems may “masquerade” as being in P—since the known ones are all isomorphic, if one does they all do. This may explain the success of SAT-solvers and suspicion about P=NP being independent as voiced during the panel. It also suggests that intermediate problems may bear attacking first.
At the conclusion of the panel Agnew, who moderated it skillfully, asked the question:
If you had to state what you believe “at gunpoint” what do you believe about P vs. NP?
He was holding a Nerf gun, but we still all seemed to take the threat seriously. Not surprisingly, all but one “fool” said that they believed that P is not equal to NP. The sole fool, me, said that they felt that P=NP. I have stated this and argued it many times before: see this for more details on why.
Of course P vs. NP remains open, and again as the panel all agreed—including the fool—we need new ideas to resolve it.
[deleted sentence about “not considering P=NP”]