Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete.
Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede că izomorfismul grafurilor nu este o problemă NP-completă.