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.
Respuestas:
Parece que este es el resultado de dureza más fuerte hasta la fecha.
fuente