# Graph isomorphism complexity

- kind: problem
- status: partial
- year: 1972

**Statement.** Can graph isomorphism be decided in polynomial time?

It is one of very few natural problems that is in NP but believed to be neither in P nor NP-complete. Babai's quasipolynomial algorithm was the biggest advance in decades. A bug found in 2017 was fixed within days. Whether polynomial time is possible is open.

Closed 2015, László Babai: quasipolynomial time.

## Sources

- [Wikipedia: Graph isomorphism problem](https://en.wikipedia.org/wiki/Graph_isomorphism_problem)

[Complexity classes](/wiki/Space:complexity.md) · [Computation](/wiki/Continent:computation.md)

---
Revision 63, 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/Problem:graph-isomorphism?action=history. Edit: POST /api/wiki/page/Problem:graph-isomorphism {source, summary, base_rev: 63}.