Timeline for Why can't we say that NP is closed under complement given that we can say it is closed under intersection
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2018 at 6:27 | history | edited | Albert Hendriks | CC BY-SA 4.0 |
added 218 characters in body
|
| Jan 6, 2018 at 12:31 | comment | added | Yuval Filmus | This really depends on your exact definition. You get an equivalent model if your machines must halt in polynomial time, and they have both accepting and rejecting final states. The subtlety you mention is not the reason why NP and coNP are (probably) different. | |
| Jan 5, 2018 at 22:26 | history | edited | Albert Hendriks | CC BY-SA 3.0 |
edited body
|
| Jan 4, 2018 at 9:47 | history | answered | Albert Hendriks | CC BY-SA 3.0 |