to either of its well-known (and, if P ≠ NP, disjoint) subsets: P and NP-complete. It is one of only two, out of 12 total, problems listed in whose complexity remains unresolved, the other being integer factorization. It is however known that if the problem is NP-complete then the polynomial hierarchy collapses to a finite level. In November 2015, László Babai, a mathematician and computer scientist at the University of Chicago, claimed to have proven that the graph isomorphism problem is solvable in quasi-polynomial time. He published preliminary versions of these results in the proceedings of the 2016 Symposium on Theory of Computing, and of the 2018 International Congress of Mathematicians. In January 2017, Babai briefly retracted the quasi-polynomiality claim and stated a sub-exponential time complexity bound instead. He restored the original claim five days later. , the full journal version of Babai's paper has not yet been published. Its generalization, the subgraph isomorphism problem, is known to be NP-complete. The main areas of research for the problem are design of fast algorithms and theoretical investigations of its computational complexity, both for the general problem and for special classes of graphs. See also Graph homomorphism Graph automorphism problem Graph isomorphism problem Graph canonization Notes References Graph theory Graph algorithms Morphisms