People always talk about “P vs NP” like P problems are easy and NP problems are hard. This is a useful day-to-day model but also an oversimplification.

Problems can get way, way harder than NP.

(If you want a brief refresher on P and NP, check out my post NP-Complete isn’t (always) Hard.)

PSPACE-complete

P is the set of all problems that can be solved in polynomial time, relative to the input. PSPACE is the set of all problems that can be solved with polynomial space. It’s assumed, but not proven, that PSPACE is strictly larger than NP. In other words, there are some problems that take polynomial space to solve but nonpolynomial time to verify.

The canonical NP problem is quantified satisfiability. The normal SAT problem, which is NP-complete, is finding assignments to variables that satisfy a set of boolean clauses:

some ABCDEF:
  A | C
  !A | D | !E
  B | !D | E | F
  etc

The QSAT analog adds the forall and some quantifiers:

forall A:
  some BCDEF:
    A | C
    !A | D | !E
    B | !D | E | F
    etc

In other words, can we solve the problem regardless of what I choose for A? If I instead write

some BCDEF:
  forall A:
    ...

The problem is instead “is there a fixed assignment which works if A is true and if A is false?”

And, similarly to how many problems can be reduced to SAT, many problems can also be reduced to QSAT, such as finding optimal sorting networks. Many simple systems are model-checkable (showing a specification has a property) in PSPACE.

EXPTIME-complete

EXPTIME is the set of all problems that are solvable in exponential time, ie the difficult grows with O(2^n). It’s suspected that EXPTIME is strictly larger than PSPACE and NP, meaning there are problems that take more than polynomial space to solve and more than polynomial time to verify.

I looked around and most EXPTIME-complete examples fall in one of two categories. First, game problems. Given a configuration of an NxN Go/Chess/Checkers/Shogi board, does player 1 have a winning strategy?

The second, succinct circuits, are more interesting.¹ An n-node simple graph can have up to 2^n n^2 edges, meaning it takes exponential space to encode.² Some graphs can be defined algorithmically by a boolean function f(A, B) which returns whether or not nodes A and B have an edge between them. If the function is small enough,³ then we can encode the graph in polynomial space! However, because determining if two nodes are connected is no longer a cons