Complexity classes

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. ¹

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. ¹

2-EXPTIME-complete

2-EXPTIME is like EXPTIME except instead of the Big-O being $O(2^n)$, it’s $O(2^{2^n})$. ¹

ELEMENTARY-complete

ELEMENTARY is EXPTIME + 2-EXPTIME + 3-EXPTIME + (etc). ¹

TOWER-complete

Let’s define tetration ^^ as repeated exponentiation, so 3^^2 = 3^3, 3^^3 = 3^(3^3), etc. TOWER-complete, then, is O(2^^n). ¹

Ackermann-complete

Define (a variant of) the Ackermann function like this:

A(1) = 1*1 A(2) = 2^2 A(3) = 3^^3 A(4) = 4^^^4 etc

Ackermann-complete problems take time growing with O(A(n)). ¹

Hyperackermann-complete

The paper Complexity Hierarchies Beyond Elementary introduces the HAck complexity class and gives examples of it. ¹

Footnotes

1. Problems Harders than NP-Complete, ComputerThings ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷