3 ms·
Is graph isomorphism known to be in P or not in P? The article seems to suggest that it is known not to be in P, but I haven't heard anything about this.
by anonymoushn 15y ago
Is graph isomorphism known to be in P or not in P? The article seems to suggest that it is known not to be in P, but I haven't heard anything about this.
- cperciva 15y agoGraph isomorphism is one of the two big problems which are not known to be in P and also not known to be NP-complete. (Integer factorization is the other.)
- veyron 15y agoLadner's theorem established that if NP != P, then there exists "NP-easy" problems which are in NP but not in P. It has been shown that if P != NP, then GI is in that valley.
- bdhe 15y agoIt has been shown that if P != NP, then GI is in that valley. Could you point to a reference? Is this true even if P != NP, but NP = coNP?
- thesteamboat 15y agoThis pdf (http://www.cs.princeton.edu/theory/complexity/ipchap.pdf http://www.cs.princeton.edu/theory/complexity/ipchap.pdf) which is a draft chapter from a book by Arora and Barak, shows that if GI is NP-complete, then the polynomial hierarchy collapses to the second level. Collapse to the first level is when NP=coNP. So this is slightly weaker even than that.
- bdr 15y agoWikipedia disagrees: http://en.wikipedia.org/wiki/NP-intermediate http://en.wikipedia.org/wiki/NP-intermediate "In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate" "Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, however this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property."