View Single Post
Old 2015-11-11, 04:43   #3
jwaltos
 
jwaltos's Avatar
 
Apr 2012

337 Posts
Default

Heard about it and now waiting for analyses from the experts. Am pasting a paragraph from Wiki for background.

"The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP, but not known to belong 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 Garey & Johnson (1979) 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.[3]"

Last fiddled with by jwaltos on 2015-11-11 at 04:48
jwaltos is offline   Reply With Quote