3 ms·
> So if somebody found a fast solution to a NP-complete problem, pretty much all of the computationally hard problems of humanity would be solved all in one str
by FartyMcFarter 8y ago
> So if somebody found a fast solution to a NP-complete problem, pretty much all of the computationally hard problems of humanity would be solved all in one strike.
There are plenty of interesting computationally hard problems that are (probably) harder than NP-complete problems, e.g. PSPACE-complete problems. For example solving chess, or more on topic, the problem of "does this regular expression generate all strings over this alphabet"?
- mikejb 8y agoSmall but relevant nitpick: Generalized chess is EXPEPACE-complete. Standard chess has an 8x8 grid with a finite number of states. In theory, chess is solvable in constant time (because you can provide a finite lookup table).
- FartyMcFarter 8y agoIf I understand correctly it's only exptime-complete if you allow an exponential number of moves? If you only allow a polynomial number of moves then it's PSPACE-complete. But yes good point about specific board sizes :)