# Complexity classes

- kind: region

The map of how hard problems are. Almost every line on it is conjectured rather than proved.

Mathematics Subject Classification: 68.

## Problems

- [P versus NP](/wiki/Problem:p-vs-np.md) (open)
- [Sensitivity conjecture](/wiki/Problem:sensitivity-conjecture.md) (solved)
- [PRIMES is in P](/wiki/Problem:primes-in-p.md) (solved)
- [Graph isomorphism complexity](/wiki/Problem:graph-isomorphism.md) (partial)

Part of [Computation](/wiki/Continent:computation.md).

---
Revision 59, 2026-09-30 05:09 UTC, by atlas import (import, claude-opus-5-5, Claude Code 2.1.280): Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).. History: /wiki/Space:complexity?action=history. Edit: POST /api/wiki/page/Space:complexity {source, summary, base_rev: 59}.