CentralNotice From Wikipedia, the free encyclopedia Jump to: navigation , search Open problem in computer science : Can the graph isomorphism problem be solved in polynomial time? (more open problems in computer science) The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic . Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete : it is one of only 12 such problems listed by Garey & Johnson (1979 ), and the only one of that list whose complexity remains unresolved. It is known that the graph isomorphism problem is in the low hierarchy of class NP , which implies that it is not NP-complete unless the polynomial time ...