Conocimientos comunes sobre la complejidad hipotética de los problemas gráficos

Encontré dos ejemplos de dureza hipotética de algunos problemas gráficos. La dureza hipotética significa que refutar alguna conjetura implicaría la completitud NP del problema gráfico respectivo. Por ejemplo, la conjetura de Barnette establece que cada gráfico bipartito plano cúbico conectado a 3 es hamiltoniano. Feder y Subi demostraron que refutar la conjetura implicaría la completitud NP del problema del ciclo de Hamilton en los gráficos de la clase de la conjetura.

La conjetura de 5 flujos de Tutte establece que cada gráfico sin puente tiene un flujo de 5 flujos en ninguna parte. Kochol demostró que si la conjetura es falsa, entonces el problema de determinar si un gráfico cúbico admite un flujo de 5 en ninguna parte es NP completo .

¿Existen ideas comunes sobre las conjeturas anteriores que explican la hipotética completitud NP de los problemas gráficos correspondientes? ¿Hay otros ejemplos de complejidad hipotética en el sentido anterior?

PD: Esto se publicó en MathoverFlow sin obtener una respuesta.

Aquí hay dos referencias para la segunda parte de su pregunta.

El artículo [1] aborda ciertos tipos de colorabilidad de gráficos dispersos con circunferencia dada . Para cada g fija , muestran que el problema de decisión asociado es trivial (cada gráfico de la clase tiene un color) o NP-completo. ¡Pero determinar cuál es el valor umbral de g sigue siendo un problema abierto difícil! Editar: Uno de los problemas considerados está relacionado con la conjetura de Jaeger, que cada gráfica plana de circunferencia 4 k admite un homomorfismo a C 2 k + 1$g$$g$$g$
$4k$$C_{2k+1}$. En [1] se muestra que cualquier contraejemplo proporciona directamente una prueba de dureza. (Una conjetura similar por Klostermeyer y Zhang existe para la circunferencia impar.) Para los otros problemas considerados en [1], no hay conjetura oficial, pero para cualquier suposición sobre el valor umbral correcto que uno puede hacer, si se demuestra que es falso por un contraejemplo, este último implica directamente una prueba de dureza correspondiente.$g$

En la introducción del artículo citado anteriormente también se menciona el siguiente resultado interesante sobre SAT [2]. Está comprobado que para cada , existe una función f ( k ) tal que ( k , f ( k ) ) -SAT (es decir, k -SAT donde se produce cada variable f ( k ) veces) es trivial, pero ( k , f ( k ) + 1 ) -SAT es NP-completo. (El valor preciso de f ( k $k$$f(k)$$(k,f(k))$$k$$f(k)$$(k,f(k)+1)$$f(k)$ parece desconocido, aunque se da alguna estimación).

[1] L. Esperet, M. Montassier, P. Ochem y A. Pinlou. Una dicotomía de complejidad para la coloración de gráficos dispersos. Journal of Graph Theory 73: 85-102, 2012. enlace + PDF en el sitio web del autor

[2] J. Kratochvil, P. Savicky y Zs. Tuza Una ocurrencia más de variables hace que la satisfacción salte de trivial a NP-completa. SIAM Journal on Computing 22: 203-210, 1993. enlace

¿Existen ideas comunes sobre las conjeturas anteriores que explican la hipotética completitud NP de los problemas gráficos correspondientes?

En mi opinión, existe una clara idea común en la dirección opuesta: si las conjeturas son verdaderas, entonces los problemas correspondientes no son NP completos y resultan triviales en ambos casos (cambian de NPC a $O(1)$ )

Y la idea común es que los problemas naturales, el ciclo hamiltoniano y el flujo cero en ninguna parte en los gráficos generales, son "lo suficientemente potentes y potentes" como para "simular" eficientemente el rastro de una máquina de Turing (a la Cook-Levin). Luego comienza a agregar más y más restricciones hasta que no obtiene "potencia computacional" en absoluto.

Para mí es como agregar más y más restricciones en el gráfico de transición de una máquina Turing (o en el dispositivo de cinta de lectura / escritura) hasta que obtenga algo trivial como "el gráfico de transición no contiene un ciclo".

¿Hay otros ejemplos de complejidad hipotética en el sentido anterior?

Como (probablemente) "caso resuelto" puedo aportar mi experiencia relacionada con el problema de Rodar un dado sobre una placa etiquetada .

Hace unos años, se desconocía si los tableros completamente etiquetados pueden contener dos ciclos distintos de Amítonain ( se resolvió una conjetura de enrollamiento único para todos los tableros con longitudes laterales como máximo 8). Domotor P. (usuario domotorp aquí) y yo (independientemente) probamos que tales tableros existen y la conjetura es falsa (... tenga en cuenta que Joseph O'Rourke aún no ha actualizado su página :-).

Luego, usando ese hecho, pude demostrar que rodar un dado en un tablero completamente etiquetado con agujeros es NP-completo (la caja sin agujeros todavía está abierta); aunque este es un resultado inédito.