Timeline for Why does SAT not reduce to QBF?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 15, 2015 at 17:18 | vote | accept | revisingcomplexity | ||
| Apr 15, 2015 at 17:14 | comment | added | Tom Cornebize | Yes, sorry for that. I edited my answer. | |
| Apr 15, 2015 at 17:13 | history | edited | Tom Cornebize | CC BY-SA 3.0 |
NP-complete → NP-hard
|
| Apr 15, 2015 at 12:18 | comment | added | revisingcomplexity | Yep, I follow until the point you say it is NP-complete, which I think you mean NP-hard | |
| Apr 15, 2015 at 11:10 | comment | added | Mike B. | You only show that QBF is NP-hard, not NP-complete. If QBF were NP-complete, then NP=PSPACE. | |
| Apr 15, 2015 at 10:48 | history | answered | Tom Cornebize | CC BY-SA 3.0 |