Difference between revisions
graph-isomorphism
Status and infobox
- status:
—→ partial - kind:
—→ problem - year:
—→ 1972 - statement:
—→ Can graph isomorphism be decided in polynomial time?
Source +17 −0
+---
+title: Graph isomorphism complexity
+kind: problem
+status: partial
+year: 1972
+statement: Can graph isomorphism be decided in polynomial time?
+space: complexity
+---
+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
+
+- [Wikipedia: Graph isomorphism problem](https://en.wikipedia.org/wiki/Graph_isomorphism_problem)
+
+[[Space:complexity|Complexity classes]] · [[Continent:computation|Computation]]
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.