Math Conjectures

Graph Isomorphism in Polynomial Time

OPENLandmarkOpen problemProposed c. 1971 · Standard version

Canonical statement

Is there a deterministic polynomial-time algorithm that, given adjacency matrices of two finite simple nn-vertex graphs G,HG,H, decides whether there exists a permutation π\pi of their nn vertices satisfying
uv∈E(G)  ⟺  π(u)π(v)∈E(H)for all u,v? uv\in E(G)\iff \pi(u)\pi(v)\in E(H) \quad\text{for all }u,v?
View source LaTeX
Is there a deterministic polynomial-time algorithm that,
given adjacency matrices of two finite simple \(n\)-vertex graphs
\(G,H\), decides whether there exists a permutation \(\pi\) of their
\(n\) vertices satisfying
\[
  uv\in E(G)\iff \pi(u)\pi(v)\in E(H)
  \quad\text{for all }u,v?
\]
TCS-011:[Babai2016GI][GroheNeuen2021GI][Neuen2026GI]
Theoretical computer scienceGraph theory

Notes

The graph isomorphism problem asks for a deterministic polynomial-time algorithm that, given two finite simple graphs on nn vertices, decides whether some relabelling of the vertices of one produces the other. The question of its exact complexity took its modern shape around 1971, in the same period that produced the theory of NP-completeness, and no single first proposal is documented.

The problem occupies an unusual position: it lies in NPNP but is neither known to be solvable in polynomial time nor known to be hard. Babai proved that it can be solved in quasipolynomial time n(log⁡n)O(1)n^{(\log n)^{O(1)}} [Babai2016GI], and polynomial-time algorithms are known for many natural graph classes; the surrounding landscape, including group-theoretic and parameterized approaches, is surveyed by Grohe and Neuen [GroheNeuen2021GI] and by Neuen [Neuen2026GI].

The problem remains open: a resolution requires either a polynomial worst-case algorithm for general graphs or a hardness classification explaining why none exists.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.