¿Cuál es la dureza actual conocida del isomorfismo gráfico?

21

Inspirado por la pregunta de factoraje conocido como P-hard , me pregunto cuál es el estado actual de conocimiento similar sobre la dureza del isomorfismo gráfico. Estoy seguro de que actualmente no se sabe si GI está en P, pero:

¿Cuál es la clase más grande actualmente conocida que GI es más difícil?

(no fue respondido en una pregunta similar )

Para abordar algunos de los comentarios, quiero saber las clases máximas actualmente conocidas para las que GI, el problema está completo. Los algoritmos conocidos para GI están limitados por las funciones superpolinomiales, y es miembro de NP. Pero no se sabe que GI es P-hard. Me gustaría conocer las clases C para las que se sabe que es C-hard y, con suerte, lo más inclusivo posible.

Mitch
fuente
2
"No se respondió a una pregunta similar" ¿En serio? Creo que la respuesta de Joshua Grochow allí responde la pregunta aquí.
Tyson Williams
Mire la sección "Complejidad Clase GI" aquí: en.wikipedia.org/wiki/Graph_isomorphism_problem
Aaron Sterling
3
@Tyson y quien haya votado su comentario: creo que lo que dice Mitch es que la respuesta allí solo da límites superiores en el isomorfismo gráfico, no en la dureza del isomorfismo gráfico.
Tsuyoshi Ito
Me gustaría agregar que no veo esto como una pregunta duplicada. La respuesta de Joshua da límites superiores. Esta pregunta suena más como: "¿Es GI al menos AC0 difícil?" - Sí, de acuerdo con @ Tsuyoshi.
Aaron Sterling el
66
Para gráficos planos se sabe que está completo para L ... Ver theorie.informatik.uni-ulm.de/Personen/toran/beatcs/…
Joshua Herman

Respuestas:

22

nortedo1

Parece que este es el resultado de dureza más fuerte hasta la fecha.

Mateus de Oliveira Oliveira
fuente
excelente referencia (y con fatiga visual adicional en su página, parece ser alrededor del año 2004).
Mitch
De hecho, este es un buen artículo.
Mateus de Oliveira Oliveira