Polls And Predictions And P=NP
Comments on a poll on P=NP
Bill Gasarch is doing a poll again on the question. See his post on the Computational Complexity blog for details and the rules of how to respond to the poll.
Today we (Dick and Ken) would like to talk about truth-forecasting polls in general, and Bill’s in particular.
A Polling Tall Tale
One of the things that we have discussed several times is how wrong people tend to be in guessing the truth of mathematical statements. Here are the results of a putative old poll on the question of whether polynomial-size bounded-width branching programs could compute the majority function—or more ambitiously, evaluate a given Boolean formula on a given assignment. The latter was symbolized as the question of whether .
Let’s say the poll were conducted at the August 1983 Fundamentals of Computation Theory (FCT’83) conference on the island of Öland off the coast of Sweden. This is where the discovery of Interactive Proof Systems was presented with high regard during lunches with Ken and other participants, although it would not be accepted for publication until STOC 1985. After storms on the last day disrupted ferry service and the bridge to the mainland, the conference participants could have been reduced to eating huge piles of fresh-caught shrimp called reker, provided on condition of filling out the following questions:
- Do you think or not? You may give other answers as well—such as, can polynomial size constant width programs compute the majority function? A total of stated, “no way.” The common point was: how could a constant-width program “remember” the number of 1’s in a bit string? Impossible. Overall 61 of 70 who gave a definite answer believed .
- When do you think it will be resolved? A total of felt that it would take decades to resolve the problem. The difficulty is that in order to solve the problem a new method would have to be discovered for proving super-polynomial lower bounds. While constant-width poly-size branching programs are restricted and seem to be weak, lower bounds against them were believed difficult then—and have not been obtained in the 28 years since, either.
- What kinds of techniques do you think will be used? Many respondents cited graph-theory topics, such as concentrators and the concept of bounded tree-width. Others mentioned progress on lower bounds against constant-depth circuits. No one mentioned group theory, or any inkling that techniques over 150 years old would solve the problem.
- Will the problem still be relevant given advances in algorithms and in SAT Solvers? Back then people were dubious that constant-width BWBP’s would be important, but this was before the topic now better known as Binary decision diagrams really took off as a research subject.
To be sure, the famous theorem by David Barrington showing that in fact the classes are equal involves a quadratic size blowup in its original proof. Richard Cleve proved that the exponent can be pushed arbitrarily close to 1, but at the cost of other complications. This vastly improved an earlier result of Dick and Jin-Yi Cai.
Thus the intuition that there is no supremely practical way for BWBP’s to solve the problem may have been correct. Theory, however, first cares what is true, and wisely leaves judgments of practicality to the future.
Our Answers To Bill’s Poll
Ken has maintained his answers from the previous poll, and Dick’s are similarly the same as his opinions ten years ago. Note that they are opposite to each other. We actually haven’t tried to convince each other to either side; it is enough that we have good reasons for our views. We tend to discuss more the intermediate problems talked about further below.
The wording of Bill’s poll questions 1.–4. is the same as in our telltale tall-tale version above, except that 1. is Do you think P=NP or not? You may give other answers as well.
- Dick: P=NP. Ken: P NP.
- Dick: December , 2012. Ken: 2030–2040.
- Dick: The approach based on upper bounds, as used by Ryan Williams, seems to me to be the best chance. Ken: Algebraic geometry, including deeper aspects of cohomology theory than have been used before, for which see this 2005 survey paper by Saugata Basu, Richard Pollack, and Marie-Françoise Roy, and work by Joel Friedman linked from this StackExchange item.
- Dick: Yes, relevant. Ken: Yes, relevant—I have not yet seen a treatment of the idea that SAT instances resulting from natural reductions to SAT tend to be harder than instances of the same size that show up in test suites for these solvers.
Note that as for when P vs. NP will be resolved, both of us feel “The End Is Near”—2030 is only 19 years away, now compare that the “Natural Proofs” paper by Alexander Razborov and Stephen Rudich was almost 19 years ago. It seems to follow that any civilization advanced enough to contact us, such as the Vegans in Carl Sagan’s novel Contact, or the Vogons in the Hitchhiker novels, would already know the answer. We differ on whether they would tell us the answer, with Dick saying yes, just before sending us off to coincide with the Mayan quinquemillennium.
Bill’s Other Question
Bill has included another question besides 4. that was not part of his original poll ten years ago:
5. Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem.
Here are our comments—you are welcome to follow up in the comments section of this blog post, but then please also communicate them in direct response to Bill.
- Dick: Factoring is in . Actually let’s go all the way and guess that it is in polynomial time. As to when it will be done, I think there are two times: when it is solved and when it is made public. The first is now, and the second is 2020.
- Ken: Graph Isomorphism is in P. Am sympathetic to the view that Factoring is in P, or at least in BPP. Not sure I believe the strong hypothesis of size lower bounds on non-uniform circuits for problems in exponential time, on which major de-randomization results are based. Something tells me a upper bound may be possible. I believe that when scalability of quantum computers is understood in full light of physical theory, the standard quantum-circuit model will be found to be over-optimistic by a quadratic factor. Generally I agree with Gil Kalai’s suspicions—note the new paper in his “How Quantum Computers [Can] Fail” series, and his slides for seminars he gave last January. I believe that super-linear circuit size lower bounds for some problem in will come first.
Mind you, all of these projected answers should be treated as “quantum noise”—we aren’t even calling them predictions. To quote Anil Nerode’s remarks in Bill’s original poll:
Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.
What are your guesses? Please remember to send your answers directly to Bill.
Also, what questions would you add to the poll?
[made clearer the BWBP poll is a tall tale.]