Exit P versus NP Survey Do you think P = NP? Question Title * 1. Do you think P = NP? Yes No Comments (or a different answer) When do you think the question will be resolved? Question Title * 2. When do you think the question will be resolved? 2018-29 2030-39 2040-49 2050-59 2060-69 2070-79 2080-89 2090-99 2100-2199 2200-2299 2300- P=NP will never be resolved Comments (or a different answer) (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 * 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.) P=NP P≠NP Comments (or a different answer) What kind of mathematics will be used to resolve P vs NP? Question Title * 4. What kind of mathematics will be used to resolve P vs NP? Do you think the polynomial hierarchy collapses (i.e., for some i, Σ^{p}_{i}=Σ^{p}_{i+1})? Question Title * 5. Do you think the polynomial hierarchy collapses (i.e., for some i, Σ^{p}_{i}=Σ^{p}_{i+1})? Yes No Comments (or a different answer) Do you think that SAT has polynomial-sized circuits? Question Title * 6. Do you think that SAT has polynomial-sized circuits? Yes No Comments (or a different answer) Do you think P=BPP? Question Title * 7. Do you think P=BPP? Yes No Comments (or a different answer) Do you think that SAT∈BQP (commonly called Quantum P) implies that the polynomial hierarchy collapses? Question Title * 8. Do you think that SAT∈BQP (commonly called Quantum P) implies that the polynomial hierarchy collapses? Yes No Comments (or a different answer) Do you think P = NP∩coNP? Question Title * 9. Do you think P = NP∩coNP? Yes No Comments (or a different answer) Do you think that Graph Isomorphism is in P? Question Title * 10. Do you think that Graph Isomorphism is in P? Yes No Comments (or a different answer) Do you think factoring is in polynomial time? Question Title * 11. Do you think factoring is in polynomial time? Yes No Comments (or a different answer) 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, 1^{t}⟩| nondeterministic N does not halt on input x within t steps}, there exists ⟨N',x'⟩ such that the runtime of M on ⟨N',x',1^{t}⟩ is not bounded by a polynomial t^{c}? 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, 1^{t}⟩| nondeterministic N does not halt on input x within t steps}, there exists ⟨N',x'⟩ such that the runtime of M on ⟨N',x',1^{t}⟩ is not bounded by a polynomial t^{c}? Yes No Comments (or a different answer) If someone shows P=NP, will this have a big effect on practical computing? Question Title * 13. If someone shows P=NP, will this have a big effect on practical computing? Yes No Comments (or a different answer) 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? Yes No Comments (or a different answer) Given that SAT-solvers are now quite good, will P vs NP still be relevant? Question Title * 15. Given that SAT-solvers are now quite good, will P vs NP still be relevant? Yes No Comments (or a different answer) Aside from P vs NP, which open problem do you most want to see solved? Question Title * 16. Aside from P vs NP, which open problem do you most want to see solved? Anything else you want to comment on, feel free! Question Title * 17. Anything else you want to comment on, feel free! Do I have permission to print your response with your name? without your name? not at all? Question Title * 18. Do I have permission to print your response with your name? without your name? not at all? With your name? Without your name? Not at all? Enter your name (will not be shared without your permission): Question Title * 19. Enter your name (will not be shared without your permission): Enter your email address (will not be shared): Question Title * 20. Enter your email address (will not be shared): What is your highest degree? (The remaining questions are for statistical purposes only and will not be published.) Question Title * 21. What is your highest degree? (The remaining questions are for statistical purposes only and will not be published.) PhD Masters Bachelors Other (please specify) What is it in? Question Title * 22. What is it in? Computer Science Mathematics Other (please specify) Where is it from? Question Title * 23. Where is it from? When did you get it? Question Title * 24. When did you get it? Done