Timeline for How to prove a problem is NOT NP-Complete?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2013 at 6:28 | vote | accept | Untitled | ||
| Mar 24, 2018 at 14:27 | |||||
| Jun 21, 2013 at 14:19 | history | edited | John Kemeny | CC BY-SA 3.0 |
added 203 characters in body
|
| Jun 21, 2013 at 11:52 | comment | added | John Kemeny | @Untitled You probably didn't mean coNP-completeness. One way of showing it is by my point (2), proving that the problem is NEXPTIME-hard. We know that NP $\subsetneq$ NEXPTIME, so that would prove it. Proving that a problem $Q$ is NEXPTIME-hard, would therefore mean that $Q$ cannot be in NP and thus cannot be NP-complete. | |
| Jun 21, 2013 at 11:28 | comment | added | Untitled | Oh, and I didn't mean this specific problem, because as Shaull stated, this problem is still open. I meant proving coNP-Completeness in general. | |
| Jun 21, 2013 at 11:22 | comment | added | Untitled | Both the techniques you provided lie on some kind of unproved assumption. Do think there could be a concrete way (no assumptions) of solving a problem of this kind? | |
| Jun 21, 2013 at 11:04 | history | answered | John Kemeny | CC BY-SA 3.0 |