Is graph isomorphism in P?
Babai's quasipolynomial algorithm moved the problem, but the gap to polynomial time remains.
Inferred from the community field; finer classification has not been reviewed.
Problem statement
Given two finite graphs, decide whether they are isomorphic. Is there an algorithm running in time ?
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Graph isomorphism is one of very few natural problems in NP not known to be either in P or NP-complete. It is not NP-complete unless the polynomial hierarchy collapses, by results on the complexity of the complement via interactive proofs.
Known partial results
- Babai (2015–2017) gave an algorithm running in time, quasipolynomial rather than polynomial.
- Polynomial-time algorithms exist for graphs of bounded degree (Luks), bounded genus, bounded treewidth, and for excluded-minor classes.
- The group-theoretic bottleneck is the string isomorphism problem, which Babai's analysis addresses via the split-or-Johnson routine.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.