3 ms·
A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.
by baddox 16y ago
A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.
- derefr 16y agoIf it was verifiable in NP time, and P = NP, then wouldn't it also be verifiable in polynomial time?
- baddox 16y agoIs that correct? I'm not sure. NP problems are verifiable in deterministic polynomial time. That includes the hardest of NP problems (NP-complete problems, e.g. travelling salesman and graph coloring). Are there problems that are "harder" than that? I never learned about anything outside NP—I know there are other complexity classes out there (like probabilistic classes), but I don't know how they compare to NP. My guess is that anything outside NP is essentially a non-deterministic problem altogether, meaning the "answer" isn't formally a simple "yes" or "no."
- ent 16y agobut wouldn't it be just plain NP then
- niczar 16y ago"NP time" doesn't mean anything. NP problems are verifiable in polynomial time.