Timeline for If a problem is not in NP, prove that every NP problem can be efficiently reduced to it
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2019 at 16:04 | history | edited | Hermann Gruber | CC BY-SA 4.0 |
Correction; added 166 characters in body
|
| Oct 24, 2019 at 15:38 | comment | added | Hermann Gruber | Ah, thanks. It was EXPSPACE what I had in mind. That is provably different from PSPACE and thus from NP because of the space hierarchy theorem. | |
| Oct 23, 2019 at 21:06 | comment | added | Tom van der Zanden | It is possible that EXPTIME=NP so this does not fully answer the question. | |
| Oct 23, 2019 at 21:05 | history | answered | Hermann Gruber | CC BY-SA 4.0 |