Qual é a dureza atualmente conhecida do isomorfismo gráfico?

21

Inspirado pela pergunta que o fatorial é conhecido como P-duro , pergunto-me qual é o atual estado similar de conhecimento sobre a dureza do isomorfismo gráfico. Estou certo de que atualmente não se sabe se GI está em P, mas:

qual é a maior classe atualmente conhecida que a IG é mais difícil?

(não foi respondido em uma pergunta semelhante )

Para abordar alguns dos comentários, quero conhecer as classes máximas atualmente conhecidas para as quais GI, o problema está completo. Os algoritmos conhecidos para GI são limitados por funções superpolinomiais e são membros do NP. Mas não se sabe que o IG é difícil. Gostaria de conhecer todas as classes C para as quais é conhecido como C-difícil e, esperançosamente, o mais inclusivo possível.

Mitch
fonte
2
"não foi respondido em uma pergunta parecida semelhante" Sério? Acho que a resposta de Joshua Grochow lá responde à pergunta aqui.
Tyson Williams
Veja a seção "Complexity Class GI" aqui: en.wikipedia.org/wiki/Graph_isomorphism_problem
Aaron Sterling
3
@Tyson e quem votou positivamente no seu comentário: Acho que o que Mitch está dizendo é que a resposta só dá limites superiores ao isomorfismo do gráfico, não à dureza do isomorfismo do gráfico.
Tsuyoshi Ito
Gostaria de acrescentar que não vejo isso como uma pergunta duplicada. A resposta de Josué dá limites superiores. Essa pergunta soa mais como "GI é pelo menos AC0 difícil?" - sim, concorde com @Tsuyoshi.
Aaron Sterling
6
Para gráficos planares, sabe-se que ele é completo para L ... Veja theoryie.informatik.uni-ulm.de/Personen/toran/beatcs/…
Joshua Herman

Respostas:

22

O isomorfismo gráfico é difícil para a DET, a classe de problemas que são redutíveis ao determinante. Veja "Sobre a dureza do isomorfismo de grafos", de Jacobo Toran. http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=noNC1

Parece que este é o resultado de dureza mais forte até o momento.

Mateus de Oliveira Oliveira
fonte
uma excelente referência (e com um esforço extra nos olhos em sua página, parece ocorrer por volta de 2004).
Mitch
De fato, este é um bom artigo.
Mateus de Oliveira Oliveira