# P3112: Is graph isomorphism solvable in polynomial time?

- ID: `P3112`
- Reference: `graph-isomorphism-in-p`
- Page: https://theoremdb.org/statements/P3112
- Record maturity: Reviewed problem with recorded work

## Problem

Is there a deterministic algorithm that, given two finite simple graphs on \(n\) vertices, decides whether they are isomorphic in time \(n^{O(1)}\), equivalently is graph isomorphism in \(\mathrm P\)?

### Context

Known frontier: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located.

Open boundary: A polynomial-time bound remains open.

### Problem setup

- **Definition (graph isomorphism).** A vertex bijection preserving adjacency in both directions.
- **Definition (quasipolynomial time).** Time exp((log n)^{O(1)}).
- **Remark.** Graph isomorphism has strong practical solvers and a quasipolynomial worst-case algorithm. It is neither known NP-complete nor known to lie in P.

### What counts as a solution

- Give and prove a deterministic polynomial-time isomorphism algorithm.
- Or prove no such algorithm exists in a stated standard model, which would separate complexity classes.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located. Exact unresolved remainder: A polynomial-time bound remains open. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located. Exact unresolved remainder: A polynomial-time bound remains open.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located.

The exact unresolved remainder is: A polynomial-time bound remains open.

A complete resolution must meet the following acceptance conditions:
- Give and prove a deterministic polynomial-time isomorphism algorithm.
- Or prove no such algorithm exists in a stated standard model, which would separate complexity classes.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located. Exact unresolved remainder: A polynomial-time bound remains open.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: graph isomorphism polynomial time open 2026; best general graph isomorphism algorithm quasipolynomial
- Strongest checked neighboring result: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located.
- Exact unresolved remainder: A polynomial-time bound remains open.

### Other known results

- **Claim 2** (supported): Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Babai's deterministic quasipolynomial-time algorithm is the best general worst-case bound located. Unresolved remainder: A polynomial-time bound remains open. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): A polynomial-time bound remains open.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `graph-isomorphism-in-p`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>László Babai, “Graph isomorphism in quasipolynomial time [extended abstract]”. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016), 684-697. DOI 10.1145/2897518.2897542. main theorem https://arxiv.org/abs/1512.03547
   - Also cited at abstract and theorem
   - Also cited at L. Babai, Graph isomorphism in quasipolynomial time, STOC 2016. main theorem
   - preprint; primary source; arXiv:1512.03547, checked 2026-08-01; checked 2026-08-01
   - Source use: original_summary
   - Gives the exp(polylog n) general algorithm.
   - Durable proceedings record for the current general upper bound.
   - Source used to assess the problem's recorded status.
   - For Is graph isomorphism solvable in polynomial time?: This is the dated publication status for the canonical target Is graph isomorphism solvable in polynomial time?.
   - Source named by the research packet.
2. <a id="reference-2"></a>Martin Grohe and Daniel Neuen, “Recent Advances on the Graph Isomorphism Problem”. arXiv:2011.01366 (2021). Introduction, pp. 1-2, and concluding open questions https://arxiv.org/abs/2011.01366
   - preprint; secondary source; arXiv:2011.01366v2; checked 2026-08-01
   - Source use: original_summary
   - Surveys the quasipolynomial frontier and explicitly records polynomial-time graph isomorphism as the main open question.