Timeline for A dense NP complete language implies P=NP
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2013 at 11:17 | vote | accept | Jernej | ||
| Feb 5, 2013 at 23:45 | answer | added | Kaveh | timeline score: 6 | |
| Feb 2, 2013 at 21:34 | answer | added | Reza | timeline score: 3 | |
| Feb 1, 2013 at 4:40 | comment | added | Yuval Filmus | @PålGD Turn into an answer? (assuming the argument carries over to dense languages) | |
| Jan 31, 2013 at 13:55 | history | tweeted | twitter.com/#!/StackCompSci/status/296979979491741696 | ||
| Jan 30, 2013 at 20:19 | comment | added | John K. | Check out Mahaney's theorem. | |
| Jan 30, 2013 at 20:11 | comment | added | Yuval Filmus | There is a related notion of sparse languages, in which the condition is just the opposite: $|J \cap \Sigma^n| \leq p(n)$. | |
| Jan 30, 2013 at 20:07 | history | asked | Jernej | CC BY-SA 3.0 |