- Does P=NP? I think P is NOT NP. However, I am not dogmatic on this. When I first saw the Graph Minor Theorem used to get Vertex Cover for fixed k into O(n3) times I thought that a different very-hard-math-thing-that-I-don't-understand might be able to get SAT in P. Also, I am more convinced that separating the two is hard then I am convinced that they are different. Litmus test: If someone told me that the problem had been solved, but not which direction, I would guess P=NP. SIDE NOTE: My wife thinks P is NOT NP since If P=NP then they would have proven it by now. This argument may become more compelling as time goes on.
- When do you think it will be resolved? Between 200 and 400 years from now. Jon Katz told me: If its not solved within 200 years its not going to be solved..
What kinds of techniques will be used?
- Fermat didn't know about Elliptic Curves. Similarly, we do not know the techniques.
- I hope its Ramsey Theory and Logic so I might understand the proof.
- If it comes out of Geometric Complexity Theory I will not understand the proof.
- We will show that P ≠ NP by showing that FACTORING is not in P. SAT might not be a good candidate for separation. This kind of thing has happened before (once): The proof that AC0 ≠ NC1 was done by showing PARITY not in AC0. PARITY is not complete for NC1 under AC0 reduction. The word problem for S5 is, but was not useful for separation. Factoring may be a better candidate for separation since you can generate instances that seem hard, where for SAT this seems hard to do.
- Ryan Williams great result shows that there are still things we can do with what we know now. Is P vs NP one of them? NO.
- Will the problem still be relevant given advances in SAT solvers? YES. Sat Solvers are GREAT and can solve lots of things- perhaps more than we had thought. But there are still lots that are not. The 17x17 problems has resisted attempts by SAT solvers to solve it (or so I've been told). The problem is a 4-CNF with 4 × 172 vars (not that many), and roughly 4 × 174clauses (too many).
Feel Free to comment on other things:
- Graph Isomorphism: We will show P ≠ NP but still not know the status of GI. OR we could find that GI is in P tomorrow.
- As noted above, we will show Factoring is NOT in P.
- Quantum Computers will never be practical; however, see next note.
- Just as the Prob Method is now a STANDARD thing to know even if you are not working on probability, Quantum methods will be a standard thing to know even if you don't work on quantum computing.
- We will show L=RL before I do this poll again.
- Within 10 years all supermarkets will have self-checkouts that work nicely and that you are expected to use--- except in New Jersey which will outlaw them to create more jobs (as they do now for self-service gas).
Friday, November 11, 2011
My response to the Gasarch P vs NP poll
A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers.