¿Qué tan común es la transición de fase en problemas con NP completo?

17

Es bien sabido que muchos problemas NP-completos exhiben transición de fase. Estoy interesado aquí en la transición de fase con respecto a la contención en el lenguaje, en lugar de la dureza de la entrada, en relación con un algoritmo.

Para que el concepto no sea ambiguo, definamos formalmente lo siguiente. Una lengua exhibe transición de fase (con respecto a la contención), siL

  1. Hay un parámetro de orden , que es una función de tiempo real polinomial computable, de valor real de la instancia.r(x)

  2. Hay un umbral . Es una constante real o puede depender de, es decir, .n = | x | t = t ( n )tn=|x|t=t(n)

  3. Para casi todos los con , tenemos x L . ( Casi todos los medios aquí: casi todos , es decir, la proporción se aproxima a 1, como n ).r ( x ) < txr(x)<txLn

  4. Para casi todas las x con r(x)>t , tenemos xL .

  5. Para casi cada x , sostiene que r(x)t . (Es decir, la región de transición es "estrecha").

Muchos problemas naturales de NP completo exhiben transición de fase en este sentido. Los ejemplos son numerosas variantes de SAT, todas las propiedades de gráficos monótonos, varios problemas de satisfacción de restricciones y probablemente muchos otros.

Pregunta: ¿Cuáles son algunas excepciones "agradables"? ¿Existe un problema natural de NP completo, que (probablemente) no tiene una transición de fase en el sentido anterior?

Andras Farago
fuente
1
Probablemente desee reformular la condición 5, ya que eso puede evitarse fácilmente agregando un poco de ruido a t para asegurarse de que no sea igual a r(X) para ninguna X . Restringiendo r para que sea una función yt = 0 (ambas cosas pueden hacerse wlog), un contraejemplo necesitaría ser un problema NP completo que ningún algoritmo (el que calcula r ) puede adivinar de manera confiable, es decir, es difícil incluso con instancias elegidas de la distribución uniforme. Supongo que pretendías que r no tuviera tanto poder expresivo. ±1t=0 0rr
Yonatan N
Entonces, si define una transición de fase, como se indicó anteriormente, existen instancias difíciles, con alta probabilidad: en el caso de problemas completos de NP, el problema es estudiar tal vez alguna propiedad (prueba) del problema, de modo que es muy probable que haya instancias difíciles. Por el contrario, si hubiera una prueba, hay instancias fáciles, con alta probabilidad. Por ejemplo, un gráfico aleatorio puede tener una densidad de borde cerca de la transición de fase que podría afectar la facilidad de solución de los problemas.
user3483902

Respuestas:

4

Los investigadores expertos en esta área básicamente afirman que las transiciones de fase son una característica universal de los problemas completos de NP, aunque esto aún no se ha formulado / probado rigurosamente y aún no se considera / disemina ampliamente en el campo más amplio (emana más de una orientación empírica rama de estudio). Es casi una conjetura abierta. Hay una fuerte evidencia. no hay candidatos plausibles para problemas completos de NP sin transición de fase. Aquí hay dos referencias que admiten este punto de vista:

Aquí hay un bosquejo de la verdad de la afirmación. tiene que ver con P contenido en NP completo. un problema / lenguaje completo de NP debe tener instancias que se puedan resolver en tiempo P y otras que se puedan resolver en tiempo exponencial (o al menos superpolinomial) si P ≠ NP. pero siempre debe haber alguna forma de "agrupar" las instancias P de las instancias "no P". por lo tanto, siempre debe haber algunos "criterios de transición" entre las instancias P y no P en resumen, ¡tal vez este fenómeno está intrínsecamente acoplado con P ≠ NP!

Otro argumento aproximado: todos los problemas completos de NP son intercambiables mediante reducciones. Si se encuentra una transición de fase en una sola, debe encontrarse en todas ellas.

Más evidencia circunstancial de esto, más recientemente (~ 2010) se demostró que la transición de fase se muestra para los límites inferiores en los circuitos monótonos para la detección de camarillas en gráficos aleatorios.

divulgación completa: Moshe Vardi ha estudiado las transiciones de fase, particularmente en SAT y tiene una visión más escéptica en contraste en esta charla / video.

vzn
fuente
2
Buen enlace en la charla de Moshe Vardi, ¡gracias! Solo para llevar el punto a casa, la transición de fase de un conjunto NP-Complete no implica una dificultad en la complejidad de la instancia. M. Vardi no lo menciona, pero la propagación de encuestas resuelve instancias con millones de variables / cláusulas cerca del umbral crítico (en el extremo positivo) para 3SAT y se sabe desde hace un tiempo que hay algoritmos de tiempo polinomiales casi seguros para el ciclo HAM en Erdos -Renyi gráficos aleatorios.
user834
0

solnorte,metronortemetro(norte2)metrosolnorte,metro

usuario3483902
fuente
2
El documento vinculado muestra exactamente lo contrario, que la transición de fase de los ciclos hamiltonianos en los gráficos aleatorios de Erdos-Renyi muestra una transición de fase (en la probabilidad de que aparezca un ciclo hamiltoniano) pero no muestra una recuperación significativa en la dificultad computacional. Es bien sabido que existen algoritmos de tiempo polinomiales probabilísticos casi seguros para los gráficos aleatorios de Erdos-Renyi, en todas partes en la transición de fase, incluso en el umbral crítico. Lo siento, pero tengo que dar un voto negativo por esta respuesta.
user834
-1

La coloración C de los gráficos regulares D tiene una serie de transiciones discretas, no particularmente escalonadas, a menos que se estire.

Aquí hay una tabla de resultados para colorear que enviaré a SAT17. Tenga en cuenta que 3 colores de 6 gráficos regulares es imposible, excepto por algunos ejemplos. Del mismo modo, 4 colores de gráficos de décimo grado ... los gráficos C3D5N180 son ligeramente difíciles. El C4D9 Golden Point solo está tentativamente en C4D9N180; Los gráficos C4D9 son los 4cnfs más difíciles por tamaño que he encontrado, por lo que C4D9 califica como un "punto duro". Se conjetura que existe el punto dorado C5D16, pero estaría en la región del punto duro de 5 a 6 colores.

          Universal Constants of Regular Graph Coloring

Las fórmulas para colorear tienen variables lgC por vértice, para un total de variables lgC * N; los bordes tienen cláusulas de coloración C, para un total de cláusulas C * M. Hay algunas cláusulas adicionales por vértice para descartar colores adicionales. Los Golden Points son el N más pequeño de tal manera que: la colorabilidad C en gráficos de grado D con N vértices es casi siempre satisfactoria, con una probabilidad cercana a 1. Para alta probabilidad, N instancias aleatorias fueron satisfactorias. Para Very High, N * N fueron satisfactorios. Para Super High, las instancias aleatorias N * N * N 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 * N)) son:

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

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

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

Todas las instancias aleatorias en el estudio fueron satisfactorias. Los puntos de probabilidad lineal verificaron cientos de fórmulas satisfactorias. Los puntos de probabilidad cuadráticos verificaron decenas de miles de fórmulas satisfactorias. Los puntos de probabilidad cúbicos verificaron cientos de miles de fórmulas satisfactorias. Los puntos C4D9 y C5D13 son difíciles. Se conjetura que el punto C5D16 existe. Una instancia aleatoria de decimosexto grado de cinco colores demostraría la conjetura.

daniel pehoushek
fuente