Timeline for Proving NP completness without reductions
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2015 at 19:22 | history | tweeted | twitter.com/#!/StackCompSci/status/598568931956269056 | ||
| May 13, 2015 at 14:37 | comment | added | cody | @Raphael: I'm not sure what you mean by your comment: showing that a problem is NP complete can be done by reducing to a single NP complete problem. However, the process has to start somewhere! In particular, you need to know that there is at least one NP-complete problem. Historically, this problem was "The language of Turing machines that halt in a given polynomial time for all input". It was shown that every NP problem is reducible to this one, and that this problem was reducible to SAT. | |
| May 12, 2015 at 6:42 | comment | added | Raphael | Since NP-completeness is defined in terms of the reduction, probably not. But there may be. | |
| May 12, 2015 at 6:41 | history | edited | Raphael | CC BY-SA 3.0 |
edited tags
|
| May 11, 2015 at 22:12 | answer | added | David Richerby | timeline score: 5 | |
| May 11, 2015 at 21:08 | review | First posts | |||
| May 12, 2015 at 2:26 | |||||
| May 11, 2015 at 21:06 | history | asked | jon Prime | CC BY-SA 3.0 |