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.