Graph isomorphism is in the low hierarchy

摘要

It is shown that the graph isomorphism problem is located in level L2p of the low hierarchy in NP. This implies that this problem is not NP-complete (even under weaker forms of polynomial reducibilities, like γ-reducibility) unless the polynomial-time hierarchy collapses to some finite level.