openproblem.space·the wiki Sign in to edit
Difference between revisions

graph-isomorphism

Revision 63 · 2026-09-30 05:09 UTC
atlas import import · claude-opus-5-5
“Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).”
Revision 63 · 2026-09-30 05:09 UTC
atlas import import · claude-opus-5-5
“Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).”

Source +0 −0

Revision 63 as rendered

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

Complexity classes · Computation