Question Title

* 1. Do you think P = NP?

Question Title

* 3. (Answer this question only if you answered P≠NP above.) Sasha Razborov, Avi Wigderson, and Andy Yao (or three other wise people whose opinions on P vs NP you take seriously) knock on your door at 3 a.m. to tell you that P vs NP has been resolved — but after announcing it dash off to tell Lane the good news — without telling you in which direction or how it had been resolved! Which way do you think it went? (This question measures what is stronger: your belief that P≠NP or your belief that we are no where near proving P≠NP.)

Question Title

* 4. What kind of mathematics will be used to resolve P vs NP?

Question Title

* 5. Do you think the polynomial hierarchy collapses (i.e., for some i, Σpipi+1)?

Question Title

* 6. Do you think that SAT has polynomial-sized circuits?

Question Title

* 7. Do you think P=BPP?

Question Title

* 8. Do you think that SAT∈BQP (commonly called Quantum P) implies that the polynomial hierarchy collapses?

Question Title

* 9. Do you think P = NP∩coNP?

Question Title

* 10. Do you think that Graph Isomorphism is in P?

Question Title

* 11. Do you think factoring is in polynomial time?

Question Title

* 12. If you answered P≠NP above, do you believe that an obstacle is "hard instances", for example, for any deterministic Turing machine M accepting the language L={⟨N, x, 1t⟩| nondeterministic N does not halt on input x within t steps}, there exists ⟨N',x'⟩ such that the runtime of M on ⟨N',x',1t⟩ is not bounded by a polynomial tc?

Question Title

* 13. If someone shows P=NP, will this have a big effect on practical computing?

Question Title

* 14. If someone shows P≠NP, will this have a big effect on practical computing?

Question Title

* 15. Given that SAT-solvers are now quite good, will P vs NP still be relevant?

Question Title

* 16. Aside from P vs NP, which open problem do you most want to see solved?

Question Title

* 17. Anything else you want to comment on, feel free!

Question Title

* 18. Do I have permission to print your response with your name? without your name?
not at all?

Question Title

* 19. Enter your name (will not be shared without your permission):

Question Title

* 20. Enter your email address (will not be shared):

Question Title

* 21. What is your highest degree? (The remaining questions are for statistical purposes only and will not be published.)

Question Title

* 22. What is it in?

Question Title

* 23. Where is it from?

Question Title

* 24. When did you get it?

T