Timeline for An one-sentence proof of P ⊆ NP
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2016 at 17:13 | comment | added | Sarvottamananda | Gary & Johnson use different definition for NP, but they use simple proof (just a mention) to show that $P \subseteq NP$, basically ignore the guess string. The certificate definition is used in Arora and Barak, they also use simple proof (just a hint) for $P \subseteq NP$, which basically ignores the certificate. Hopcroft an Ullman use different definition for NP, and they ignore non-determinism to prove $P \subseteq NP$ (just a mention in the text, that it can be done). | |
| May 23, 2016 at 1:49 | history | edited | Wei-Cheng Liu | CC BY-SA 3.0 |
definition -> definitions
|
| May 23, 2016 at 1:36 | history | edited | Wei-Cheng Liu | CC BY-SA 3.0 |
provide -> provides
|
| May 23, 2016 at 1:13 | comment | added | Wei-Cheng Liu | @Shreesh Could you please tell me where can I find these one-line proofs? Thank you very much. | |
| May 22, 2016 at 9:08 | vote | accept | Wei-Cheng Liu | ||
| May 20, 2016 at 22:35 | history | tweeted | twitter.com/StackCompSci/status/733788355926855680 | ||
| May 20, 2016 at 13:01 | comment | added | Sarvottamananda | For almost every equivalent definitions of $P$ and $NP$, there are one line proofs for $P \subseteq NP$. | |
| May 20, 2016 at 12:16 | history | edited | Raphael | CC BY-SA 3.0 |
deleted 5 characters in body; edited tags; edited title
|
| May 20, 2016 at 10:26 | answer | added | xavierm02 | timeline score: 3 | |
| May 20, 2016 at 10:11 | comment | added | adrianN | yes it should be a $\times$ | |
| May 20, 2016 at 10:11 | answer | added | adrianN | timeline score: 13 | |
| May 20, 2016 at 9:22 | history | asked | Wei-Cheng Liu | CC BY-SA 3.0 |