Skip to main content
1 of 1
Post Made Community Wiki

No EXPTIME-complete problem can be solved in polynomial time as a consequence of the time hierarchy theorem. Of course, the same holds for harder problems, such as problems complete for exponential space, doubly exponential time, etc. These results are unconditional (i.e., they do not depend on PNP or other conjectures).

There are some interesting problems which provably lie outside P; one of them concerns the equivalence of regular expressions (see these slides for an introduction), and some kinds of game are also very hard to solve.