¿Se mantuvo "Donde están los problemas realmente difíciles"? ¿Cuáles son las ideas actuales sobre el tema?

Este artículo me pareció muy interesante. Para resumir: analiza por qué en la práctica rara vez se encuentra el peor de los casos de un problema de NP completo. La idea en el artículo es que las instancias generalmente están muy poco o muy restringidas, las cuales son relativamente fáciles de resolver. Luego propone para algunos problemas una medida de "restricción". Esos problemas parecen tener una 'transición de fase' de 0 probabilidad de una solución a 100% de probabilidad. Luego plantea la hipótesis:

1. Que todos los problemas de NP completo (o incluso todos los problemas de NP) tienen una medida de "restricción".
2. Que para cada problema de NP completo, puede crear un gráfico de la probabilidad de que exista una solución en función de la 'restricción'. Además, ese gráfico contendrá una transición de fase donde esa probabilidad aumenta rápida y dramáticamente.
3. Los peores casos de los problemas de NP completo se encuentran en esa transición de fase.
4. El hecho de si un problema radica en esa transición de fase sigue siendo invariable bajo la transformación de un problema de NP completo a otro.

Este documento fue publicado en 1991. Mi pregunta es si hubo alguna investigación de seguimiento sobre estas ideas en los últimos 25 años. Y si es así, ¿cuál es el pensamiento dominante actual sobre ellos? ¿Fueron encontrados correctos, incorrectos, irrelevantes?

Aquí hay un resumen aproximado del estado basado en una presentación dada por Vardi en un taller sobre teoría de modelos finitos y algorítmicos (2012):

Se observó que las instancias difíciles se encuentran en la transición de fase de una región insuficiente a una limitada. La conjetura fundamental es que existe una fuerte conexión entre las transiciones de fase y la complejidad computacional de los problemas de NP.

Achlioptas – Coja-Oghlan, descubrió que hay una densidad en la región de satisfacción donde el espacio de la solución se fragmenta exponencialmente en muchos grupos pequeños. Vinay Deolalikar basó su famoso intento de probar en el supuesto de que la destrucción implica dureza computacional. La prueba de Deolalikar fue refutada por el hecho de que XOR-SAT está en $P \ne NP$$P$ y se rompe. Por lo tanto, la destrucción no se puede utilizar para demostrar la dureza computacional.

El pensamiento dominante actual parece ser (como lo afirma Vardi) que las transiciones de fase no están intrínsecamente conectadas a la complejidad computacional.

Finalmente, aquí hay un artículo publicado en Nature que investiga la conexión entre las transiciones de fase y la dureza computacional de K-SAT.

Sí, ha habido mucho trabajo desde el artículo de 1991 de Cheeseman, Kanefsky y Taylor.

Hacer una búsqueda de revisiones de las transiciones de fase de los problemas de NP-Complete le dará muchos resultados. Una de esas revisiones es Hartmann y Weigt [1]. Para una introducción de nivel superior, vea los artículos de Brian Hayes American Scientist [2] [3].

El artículo de Cheesemen, Kanefsky y Taylor de 1991 es un caso desafortunado de informáticos que no prestan atención a la literatura matemática. En el artículo de Cheeseman, Kanefsky y Taylor, identificaron que el Ciclo Hamiltoniano tenía una transición de fase con un aumento en el costo de búsqueda cerca del umbral crítico. El modelo de gráfico aleatorio que utilizaron fue el gráfico aleatorio de Erdos-Renyi (probabilidad de borde fijo o distribución de grados Gaussiana equivalente). Este caso fue bien estudiado antes del artículo de Cheeseman et all de 1991 con algoritmos de tiempo polinomiales casi seguros conocidos para esta clase de gráfico, incluso en o cerca del umbral crítico. Los "Gráficos aleatorios" de Bollobas [4] son ​​una buena referencia. La prueba original que creo fue presentada por Angliun y Valiant [5] con mejoras adicionales por Bollobas, Fenner y Frieze [6]. Después de Cheeseman,

La transición de fase para los Ciclos Hamiltonianos en gráficos aleatorios Erdos-Renyi aleatorios existe en el sentido de que hay una transición rápida de la probabilidad de encontrar una solución, pero esto no se traduce en un aumento en la complejidad "intrínseca" de encontrar Ciclos Hamiltonianos. Hay algoritmos de tiempo polinomiales casi seguros para encontrar Ciclos Hamiltonianos en gráficos aleatorios de Erdos-Renyi, incluso en la transición crítica, tanto en teoría como en la práctica.

La propagación de encuestas [8] ha tenido un buen éxito al encontrar instancias satisfactorias para 3-SAT aleatorios muy cerca del umbral crítico. Mi conocimiento actual está un poco oxidado, así que no estoy seguro de si ha habido un gran progreso en la búsqueda de algoritmos "eficientes" para casos insatisfactorios cerca del umbral crítico. 3-SAT, que yo sepa, es uno de los casos en los que es "fácil" resolver si es satisfactorio y está cerca del umbral crítico pero desconocido (¿o difícil?) En el caso insatisfactorio cerca del umbral crítico.

Mi conocimiento está un poco anticuado ahora, pero la última vez que examiné este tema en profundidad, hubo algunas cosas que me llamaron la atención:

• El ciclo hamiltoniano es "fácil" para los gráficos aleatorios de Erdos-Renyi. ¿Dónde están los problemas difíciles para ello?
• La partición de números debe poder resolverse cuando está muy lejos en la región de probabilidad 0 o 1 de probabilidad casi segura, pero no existen algoritmos eficientes (que yo sepa) incluso para tamaños de instancia moderados (1000 números de 500 bits cada uno es, hasta donde sé, completamente intratable con algoritmos de última generación). [9] [10]
• 3-SAT es "fácil" para instancias satisfactorias cerca del umbral crítico, incluso para tamaños de instancias enormes (millones de variables) pero difícil para instancias insatisfactorias cerca del umbral crítico.

Dudo en incluirlo aquí ya que no he publicado ningún artículo revisado por pares, pero escribí mi tesissobre el tema. La idea principal es que una posible clase de conjuntos aleatorios (ciclos hamiltonianos, problema de partición de números, etc.) que son "intrínsecamente difíciles" son los que tienen una propiedad de "invariancia de escala". Las distribuciones estables a Levy son una de las distribuciones más naturales con esta calidad, tienen colas de ley de potencia, y uno puede elegir instancias aleatorias de conjuntos NP-Completos que de alguna manera incorporan la distribución estable a Levy. Di algunas pruebas débiles de que se pueden encontrar instancias intrínsecamente difíciles del Ciclo Hamiltoniano si se eligen gráficos aleatorios con una distribución de grados estable de Levy en lugar de una distribución Normal (es decir, Erdos-Renyi). Si nada más, al menos le dará un punto de partida para una revisión de la literatura.

[1] AK Hartmann y M. Weigt. Transiciones de fase en problemas de optimización combinatoria: conceptos básicos, algoritmos y mecánica estadística. Wiley-VCH, 2005.

[2] B. Hayes. El problema difícil más fácil. Científico estadounidense, 90 (2), 2002.

[3] B. Hayes. En el umbral Científico estadounidense, 91 (1), 2003.

[4] B. Bollobás. Gráficos aleatorios, segunda edición. Cambridge University Press, Nueva York, 2001.

[5] D. Angluin y LG Valiant. Algoritmos probabilísticos rápidos para circuitos y emparejamientos de Hamilton. J. Computadora, Syst. Sci., 18: 155-193, 1979.

[6] B. Bollobás, TI Fenner y AM Frieze. Un algoritmo para encontrar caminos y ciclos de Hamilton en gráficos aleatorios. Combinatorica, 7: 327–341, 1987.

[7] B. Vandegriend y J. Culberson. La transición de fase G n, m no es difícil para el problema del ciclo hamiltoniano. J. of AI Research, 9: 219–245, 1998.

[8] A. Braunstein, M. Mézard y R. Zecchina. Propagación de encuestas: un algoritmo para la satisfacción. Estructuras aleatorias y algoritmos, 27: 201–226, 2005.

[9] I. Gent y T. Walsh. Análisis de heurística para partición de números. Computational Intelligence, 14: 430–451, 1998.

[10] CP Schnorr y M. Euchner. Reducción de la base del enrejado: algoritmos prácticos mejorados y resolución de problemas de suma de subconjuntos. En Proceedings of Fundamentals of Computation Theory '91, L. Budach, ed., Lecture Notes in Computer Science, volumen 529, páginas 68-85, 1991.

25 años de estudio, y dónde están las ideas actuales:

+++ idea 1:

En mi experiencia en la resolución de la satisfacción, he encontrado en la práctica que agregar una cláusula k válida a una fórmula que estamos tratando de resolver es similar a decidir una variable (nk) qbf.

¡Ese parece ser un enfoque para mostrar que los métodos actuales de resolución de sat para NP son pspace-hard!

+++ idea 2:

Otra idea es que el problema de AllQBFs es un problema real en la jerarquía booleana. El problema de AllQBF es: Producir una expresión booleana Q que decida todos los 2 ^ n qbfs de una fórmula R. AllQBFs es fácil cuando la fórmula original R es monótona o 2-cnf.

AllQBF parece un camino plausible para mostrar que QBF es Exp, porque Q es a menudo exponencial, por lo que evaluar una asignación de Q (una cuantificación de la fórmula original R) es exponencial. Entonces, el camino para probar NP es Exp, al menos tiene un par de ladrillos.

+++ idea 3: k-cnfs regulares

Por cierto, todos los estudios de transición de fase han omitido k-cnfs regulares, donde el número de ocurrencias de una variable (en cualquier dirección) es fijo, similar a los gráficos regulares de grado ... Los k-cnfs regulares se vuelven mucho más difíciles que el modelo estándar, porque todas las variables se ven idénticas en términos de restricciones sobre ellas.

Hace veinticinco años, justo después de leer Cheeseman, me concentré en la coloración de gráficos de grado regular, porque todas las variables se ven iguales. ¡Así que abusaré de mi privilegio de respuesta aquí, y presentaré veinticinco años de resultados en gráficos regulares!

+++ idea 4: Golden Points para estudios de referencia de satisfacción

He estudiado la coloración en C de D gráficos de vértices N regulares bastante extensamente. La siguiente tabla resume los resultados de Golden Point para la coloración gráfica regular.

Para alta probabilidad, N instancias aleatorias fueron satisfactorias. Para Very High, N ^ 2 fueron satisfactorios. Para Super High, N ^ 3 instancias aleatorias fueron satisfactorias.

Los puntos de coloración dorada de alta probabilidad (1 - 1 / N) son:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Los puntos de coloración dorada de probabilidad muy alta (1 - 1 / (N ^ 2)) son:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Los puntos de coloración dorada de probabilidad súper alta (1 - 1 / (N ^ 3)) son:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

La entrada C4D9 denota cuatro colores de gráficos de noveno grado. Estos son los 4cnfs aleatorios más difíciles que he encontrado en 25 años de resolución satelital. Recientemente coloreé un gráfico de noveno vértice de 172 vértices después de diez días de tiempo de CPU.

+++ Idea 5: ¿El C5D16N ???? Golden Point está ligeramente conjeturado de existir.

Gracias Daniel Pehoushek.