Graph isomorphism is in the low hierarchy (Q1116696)

The paper deals with the membership of the well known `graph isomorphism' problem in some complexity classes. Two open problems are solved. First, it is shown that `graph isomorphism' is in the class \(L^ p_ 2\) that answers the question of the author [``A low and high hierarchy within NP'', ibid. 27, 14-28 (1983; Zbl 0515.68046)]. Under the assumption that the polynomial hiearchy does not collapse to \(\sum^ p_ 2\) it is proved that `graph isomorphism' is not \(\gamma\)- complete. This answers the open problem cf. \textit{L. Adleman} and \textit{K. Manders} [``Reducibility, randomness, and intractability'', Proc. ith ACM Symp. Theory Comput. 1977, 151-163 (1977)]. Hence `graph isomorphism' is not NP-complete unless the polynomial hierarchy collapses to some finite level.