2 ms·
Graph Isomorphism is not known to be NP-hard, that is we don't know a proof that a polynomial algorithm for GI implies NP=P. So it is "at most NP" rather than "
by praptak 8y ago
Graph Isomorphism is not known to be NP-hard, that is we don't know a proof that a polynomial algorithm for GI implies NP=P. So it is "at most NP" rather than "at least NP", because GI is obviously in NP.