Problema de isomorfismo de grafos

O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos. Não é conhecido se o problema pode ser solucionável em tempo polinomial nem se é NP-completo e, portanto, pode estar na classe de complexidade computacional NP-Intermediário. Sabe-se que o problema do isomorfismo do grafo está na baixa hierarquia da classe NP, o que implica que não é NP-completo a menos que a hierarquia de tempo polinomial colapse para o segundo nível.Ao mesmo tempo, o isomorfismo para muitas classes especiais de grafos pode ser resolvido em tempo polinomial, e na prática o isomorfismo do grafo pode ser resolvido de forma eficiente. Além de sua importância prática, o problema do isomorfismo de grafos é uma curiosidade em teoria da complexidade computacional, uma vez que faz parte de um número muito pequeno de problemas pertencentes a classe NP, conhecidos por não poderem serem resolvidos em tempo polinomial e nem em NP-completo: é um de apenas 12 dos problemas listados por Garey e Johnson (1979) e o único dessa lista cuja complexidade continua não resolvida. Este problema é um caso especial do problema do isomorfismo de subgrafos , que é conhecido por ser NP-completo. É também conhecido como um caso especial do problema do subgrupo oculto não abeliano sobre o grupo simétrico.