El problema del isomorfismo gráfico es uno de los problemas más antiguos que resistió la clasificación en problemas o N P- completos. Tenemos evidencias de que no puede ser N P- completo. En primer lugar, el isomorfismo gráfico no puede ser N P- completo a menos que la jerarquía polinómica [1] se colapse al segundo nivel. Además, la versión de conteo [2] de GI es Turing en tiempo polinomial equivalente a su versión de decisión que no es válida para ningún problema completo de N P conocido . La versión de conteo de los problemas completos de N P parece tener una complejidad mucho mayor. Finalmente, el resultado de baja [3] de GI con respecto a P P ( ) no se sabe que se cumple para ningúnproblema completo de N P. El resultado de baja de IG ha sido mejorado a S P P G I = S P P después de que Arvind y Kurur demostraron que GI está en S P P [4].
¿Qué otros resultados (recientes) pueden proporcionar evidencia adicional de que GI no puede ser completo?
Publiqué la pregunta en Mathoverflow sin obtener una respuesta.
[1]: Uwe Schöning, "El isomorfismo gráfico está en la jerarquía baja", Actas del 4º Simposio anual sobre aspectos teóricos de la informática, 1987, 114-124
[2]: R. Mathon, "Una nota sobre el problema de conteo de isomorfismo gráfico", Information Processing Letters, 8 (1979) pp. 131–132
[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "El isomorfismo gráfico es bajo para PP", Complejidad computacional 2 (4): 301–330
[4]: V. Arvind y P. Kurur. El isomorfismo gráfico está en SPP, ECCC TR02-037, 2002.
fuente
Respuestas:
Debido al resultado reciente de Babai (ver el artículo ) está en tiempo cuasi polinomial ( Q P ). Si G I es N P -completo, entonces implica N P ⊆ Q P = D T I M E ( n p o l y l o gGI QP GI NP . Esto, a su vez, implicaEXP=NEXP, ver
aquí. Por lo tanto, si la conjetura comúnmente aceptadaEXP≠NEXP secumple, entoncesGIno puede serNP-completo.NP⊆QP=DTIME(npolylogn) EXP=NEXP EXP≠NEXP GI NP
fuente