NP, PSPACE, P

Complexity classes group problems by the resources needed to solve them.
Three crucial classes:

P — Polynomial time. Decision problems solvable by a deterministic
Turing machine in time $O(n^k)$ for some $k$.

Examples: reachability in graphs, primality (in P since 2002), shortest path,
sorting verification, satisfiability of Horn formulas.

NP — Nondeterministic Polynomial time. Decision problems whose YES
instances have a certificate verifiable in polynomial time. Equivalently,
solvable by a nondeterministic TM in polynomial time.

Examples: SAT (satisfiability), Hamiltonian cycle, graph coloring, TSP
(decision version), subset sum, clique.

PSPACE — Polynomial space. Problems solvable using $O(n^k)$ memory,
regardless of time. By Savitch's theorem, PSPACE = NPSPACE (nondeterministic
polynomial space).

Examples: quantified Boolean formula (QBF), game tree evaluation, regular
expression equivalence.

The chain:

The big open question: $P = NP$? Is every problem whose solution is
quickly verifiable also quickly solvable? Most experts believe $P \neq NP$,
but no proof is known — and a proof would change mathematics, cryptography,
and AI forever.

A reward of $1,000,000 from the Clay Mathematics Institute awaits a
solution. The question is one of seven Millennium Prize Problems.

Why this matters for AI. Many AI tasks — planning, scheduling, reasoning,
constraint satisfaction — are NP-complete or PSPACE-complete in the worst
case. Practical algorithms use heuristics, approximations, or special-case
structure to dodge the worst case.