Timeline for Are there any interesting examples of random NP-complete problems?
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2011 at 21:33 | comment | added | user13370 | I just came across this old paper of Steve Cook: cs.toronto.edu/~sacook/homepage/JACMpvsnp.ps It doesn't say anything directly too useful to the current discussion, but it shows that such questions have been around for a while. | |
| Jul 12, 2010 at 21:17 | answer | added | Scott Aaronson | timeline score: 28 | |
| Nov 6, 2009 at 19:14 | answer | added | Gil Kalai | timeline score: 2 | |
| Nov 6, 2009 at 13:17 | comment | added | Gil Kalai | Isnt it related to Levin's average case complexity issues? I vaguely remember that there were examples which are hard in average case but the examples were not as great as for NP completeness in worse case. | |
| Nov 3, 2009 at 12:20 | answer | added | Harrison Brown | timeline score: 1 | |
| Nov 2, 2009 at 23:11 | comment | added | gowers | I think that is indeed what I meant (if I understand you correctly). As for my motivation, I just asked it out of curiosity. | |
| Nov 1, 2009 at 17:18 | comment | added | Harrison Brown | Actually, here's a second attempt at trying to phrase what I think you're asking (for 3SAT) more formally. Please let me know if it's wrong. Let S be a "dense random collection" of 3SAT instances (I think this can be made reasonably precise). Then is there (w/h/p) a poly-time Turing reduction from every language in NP to 3SAT whose image in contained in S? | |
| Nov 1, 2009 at 17:08 | comment | added | Harrison Brown | Can I ask what motivated the question? I think there's some confusion about the "right" way to state the problem, and having some motivation might help... | |
| Nov 1, 2009 at 13:45 | answer | added | Rune | timeline score: 1 | |
| Oct 31, 2009 at 14:53 | answer | added | Steve Flammia | timeline score: 2 | |
| Oct 31, 2009 at 11:15 | answer | added | Harrison Brown | timeline score: 2 | |
| Oct 31, 2009 at 10:52 | history | asked | gowers | CC BY-SA 2.5 |