Il problema dell' isomorfismo del grafico è il problema computazionale di determinare se due grafici finiti sono isomorfi. Un importante problema irrisolto nella teoria della complessità è se il problema dell' isomorfismo grafico è in P, NP-completo o NP-intermedio. La risposta non è nota, ma si ritiene che il problema non sia perlomeno incompleto. Se l' isomorfismo grafico è NP-completo, la gerarchia temporale polinomiale crolla al suo secondo livello. Poichè si ritiene ampiamente che la gerarchia polinomiale non collassi ad alcun livello finito, si ritiene che l' isomorfismo grafico non sia incompleto. L' algoritmo migliore per questo problema, a causa di Laszlo Babai e Eugene Luks ha eseguito 2O tempo 2O (n log (n log (n)) per i grafici con n vertici.
Qual è il problema attribuito alla definizione se due grafici finiti sono isomorfici?
Il problema dell' isomorfismo del grafico isomorfismo grafico Il problema dell' isomorfismo del grafico