Alpha. curiolab.science is in early alpha testing — expect rough edges, broken links, and content that may change without notice.

Is graph isomorphism in P?

Category: Computer Science

Status: Queued

Given two graphs, decide whether one can be relabelled to look exactly like the other. The graph isomorphism problem is in NP but not known to be in P or NP-complete — a rare and famous intermediate status.

László Babai's 2015 quasi-polynomial algorithm (running in time exp((log n)^O(1))) was a major advance, but a true polynomial-time algorithm remains the open target.

Sources

Runs

No runs yet — this question is queued.