Evidencia de que el problema del isomorfismo gráfico no es

10

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 (PNPNPNPNPNPPP ) 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].PPGI=PPNPSPPGI=SPPSPP

¿Qué otros resultados (recientes) pueden proporcionar evidencia adicional de que GI no puede ser completo?NP

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.

Mohammad Al-Turkistany
fuente
8
¿Cuánta evidencia más necesitas? Permítanme cambiar la pregunta: ¿Qué evidencia hay de que GI no está en P?
Lance Fortnow
@LanceFortnow Creo que el hecho de que no tenemos siquiera un algoritmo de tiempo cuasi-polinomio para GI es la mejor evidencia de que las indicaciones geográficas no está en . ¿Eres consciente de los demás? P
Mohammad Al-Turkistany
2
La evidencia circunstancial de que GI está en P es que (afaik / afact) nadie puede construir instancias difíciles que no sean P (¿incluso al azar?) y ni siquiera parece haber candidatos (conjeturados). ps esta pregunta parece cercana a cuál es la dureza actual conocida de GI
vzn
1
@vzn Es un problema de HW demostrar que si , todos los idiomas en P, excepto y Σ , serían N P -completos (esto está bajo las reducciones de Karp). P=NPPΣNP
Mohammad Al-Turkistany
3
@Arul Ver mi comentario a VZN. Básicamente, si P = NP, entonces GI debe ser NP completo bajo reducción de Karp.
Mohammad Al-Turkistany

Respuestas:

11

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 gGIQPGINP. Esto, a su vez, implicaEXP=NEXP, ver aquí. Por lo tanto, si la conjetura comúnmente aceptadaEXPNEXP secumple, entoncesGIno puede serNP-completo.NPQP=DTIME(npolylogn)EXP=NEXPEXPNEXPGINP

Andras Farago
fuente