Complexity Classes (P, NP, PSPACE)

Complexity Classes (P, NP, PSPACE)

Complexity theory classifies problems by the resources (time and space) needed to solve them. While decidability tells us whether a problem CAN be solved, complexity theory tells us HOW HARD it is to solve. This is the practical side of theoretical computer science.

The Major Classes

P — Polynomial Time:
  Problems solvable by a deterministic TM in O(n^k)
  time for some constant k.
  Examples: sorting, shortest path, primality testing
  
  Intuition: "Efficiently solvable"

NP — Nondeterministic Polynomial Time:
  Problems where a proposed solution can be VERIFIED
  in polynomial time. Equivalently, solvable by a
  nondeterministic TM in polynomial time.
  Examples: SAT, traveling salesman (decision version),
  graph coloring, subset sum
  
  Intuition: "Efficiently checkable"

NP-Complete:
  The hardest problems in NP. If ANY NP-complete
  problem is in P, then P = NP.
  Examples: SAT (Cook-Levin theorem), 3-SAT, CLIQUE,
  VERTEX COVER, HAMILTONIAN PATH

NP-Hard:
  At least as hard as NP-complete, but not necessarily
  in NP. The halting problem is NP-hard.

PSPACE:
  Problems solvable with polynomial space.
  P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

The P vs NP Question

The most important open problem in computer science: does P = NP? In plain language: if a solution can be verified quickly, can it also be found quickly? Most computer scientists believe P ≠ NP, but nobody has proven it. This question is worth a $1 million Millennium Prize.

P = NP would mean:
  - Every problem whose solution can be verified
    quickly can ALSO be solved quickly
  - Cryptography would break (factoring is in NP)
  - Optimization problems become easy
  - Mathematical proofs could be found automatically

P ≠ NP would mean:
  - Some problems are fundamentally harder to solve
    than to verify
  - Cryptography is secure (assuming suitable
    one-way functions exist)
  - Some optimization problems have no efficient
    solution

Current status: UNKNOWN (as of 2026)

Other Complexity Classes

PSPACE:
  Problems solvable in polynomial space.
  Example: Quantified Boolean Formula (QBF)
  PSPACE-complete problems are the hardest in PSPACE.

EXPTIME:
  Problems solvable in exponential time.
  EXPTIME-complete problems provably require
  exponential time (not polynomial).

SPACE and NSPACE:
  Problems solvable in polynomial space
  (deterministic and nondeterministic).
  Savitch's Theorem: NSPACE(s(n)) ⊆ SPACE(s(n)²)

L (Logarithmic Space):
  Problems solvable in O(log n) space.
  L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Practical Impact

Complexity theory guides real-world engineering. When you choose an algorithm, you're making a complexity-theoretic decision. O(n log n) sorting beats O(n²) sorting. If a problem is NP-hard, you use approximation algorithms or heuristics instead of exact solutions. Understanding complexity classes helps you set realistic expectations and choose the right approach.