Timeline for "P vs NP" and "NP vs P/Poly"
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 8, 2011 at 0:19 | comment | added | Michal R. Przybylek | Personal belief. OP asked if NP \subset P/Poly implies \Sigma_0^p = PH. The Karp–Lipton theorem states that if NP \subset P/Poly then \Sigma_2^p = PH. I would say that this statement is ``almost'' as good as the orginal one, and its conclusion is (almost) equally unbelievable :-) | |
| Mar 7, 2011 at 22:54 | comment | added | Gerry Myerson | What does "unlikely" mean here? | |
| Mar 7, 2011 at 21:01 | vote | accept | LowerBounds | ||
| Mar 7, 2011 at 18:55 | history | answered | Michal R. Przybylek | CC BY-SA 2.5 |