Timeline for How do I construct reductions between problems to prove a problem is NP-complete?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2018 at 22:16 | comment | added | Kaveh | @Albert, well you should read it then. With Cook reductions you cannot distinguish between NP and coNP. | |
| May 5, 2018 at 22:03 | comment | added | Albert Hendriks | @Kaveh Huh? Tautology is Co-Np complete and therefore not known to be in NP(-complete). I didn't read Cook's paper though. | |
| Apr 15, 2012 at 9:41 | history | edited | Raphael | CC BY-SA 3.0 | added 29 characters in body |
| Apr 15, 2012 at 1:44 | comment | added | Kaveh | I am not sure about the claim that it is the only problem that has been proven to be NP-complete directly. In fact if you interpret it in a strict sense then it is definitely false. Cook's 1971 paper talks about TAUT not SAT (he uses Cook reductions, not Karp reductions) (it is an easy observations that the proof also proves that SAT is NP-complete under Karp reductions). | |
| Apr 14, 2012 at 18:25 | comment | added | Alex ten Brink | Directly proving that the Bounded Halting problem is NP-complete when the bound is given in unary is not too hard, and is an easy way of proving that some NP-complete problem exists, even though the problem itself is rather useless to reduce from. | |
| Apr 14, 2012 at 16:05 | history | edited | Raphael | CC BY-SA 3.0 | added 520 characters in body |
| Apr 14, 2012 at 10:25 | history | answered | Raphael | CC BY-SA 3.0 |