Ejemplos de transiciones de fase de dureza.

Supongamos que tenemos un problema parametrizado por un parámetro de valor real p que es "fácil" de resolver cuando y "difícil" cuando para algunos valores , . p = p 1 p 0 p $p=p_0$$p=p_1$$p_0$$p_1$

Un ejemplo es contar configuraciones de giro en gráficos. Contando los colores adecuados ponderados, los conjuntos independientes, los subgráficos eulerianos corresponden a las funciones de partición de los modelos hardcore, Potts e Ising, respectivamente, que son fáciles de aproximar para "alta temperatura" y difíciles para "baja temperatura". Para MCMC simple, la transición de fase de dureza corresponde a un punto en el que el tiempo de mezcla salta de polinomio a exponencial ( Martineli, 2006 ).

Otro ejemplo es la inferencia en modelos probabilísticos. "Simplificamos" el modelo dado al tomar , combinación del mismo con un modelo "todas las variables son independientes". Para el problema es trivial, para es intratable y el umbral de dureza se encuentra en algún punto intermedio. Para el método de inferencia más popular, el problema se vuelve difícil cuando el método no logra converger, y el punto en que sucede corresponde a la transición de fase (en un sentido físico) de una cierta distribución de Gibbs ( Tatikonda, 2002 ).p p = 1 p = $1-p$$p$$p=1$$p=0$

¿Cuáles son otros ejemplos interesantes del "salto" de dureza ya que se varía algún parámetro continuo?

Motivación: para ver ejemplos de otra "dimensión" de dureza además del tipo de gráfico o tipo lógico

En la aproximación estándar en el peor de los casos, hay muchos umbrales agudos ya que el factor de aproximación varía.

Por ejemplo, para 3LIN, que satisface tantas ecuaciones lineales booleanas dadas en 3 variables cada una, hay un algoritmo de aproximación de asignación aleatoria simple para la aproximación 1/2, pero cualquier aproximación mejor que alguna t = 1/2 + o (1) ya es tan duro como el SAT exacto (conjeturado para requerir tiempo exponencial).

No estoy exactamente seguro de si este es el tipo de problema que estaba buscando, pero la transición de fase de los problemas de NP-Complete es un fenómeno (por ahora) bien conocido. Vea los artículos de Brian Hayes "No se puede obtener satisfacción" sobre la transición de la fase 3-SAT y "El problema difícil más fácil" sobre la transición de la Fase de partición numérica, para algunos artículos populares sobre el tema.

Selman y Kirkpatrick fueron los primeros en mostrar numéricamente que la transición de fase para 3-SAT fue cuando la relación de cláusulas a variables fue de alrededor de 4.3.

Gent y Walsh fueron los primeros en mostrar numéricamente que la transición de fase para el problema de partición numérica ocurrió cuando la relación de bits a la longitud de la lista era de aproximadamente 1. Más tarde, esto fue analítico por Borgs, Chayes y Pittel .

El vendedor ambulante, Graph Coloring, Hamiltonian Cycle, entre otros, también parecen tener transiciones de fase para una parametrización adecuada de la creación de instancias de problemas. Creo que es seguro decir que es una creencia común que todos los problemas de NP-Complete exhiben una transición de fase para una parametrización adecuada.

Asociado a (algunos) modelos de ruido para el cálculo cuántico hay un valor umbral para el nivel de ruido, por encima del cual las puertas ruidosas pueden ser simuladas por las puertas Clifford, de modo que los procesos de cálculo cuántico se vuelvan eficientemente simulables. Para comenzar, vea Plenio y Virmani, Límites superiores en los umbrales de tolerancia a fallas de las computadoras cuánticas ruidosas basadas en Cli ff ord (arXiv: 0810.4340v1).

Los modelos solucionables como este nos informan sobre un problema práctico omnipresente: para un sistema cuántico físico específico en contacto con un depósito térmico (posiblemente a temperatura cero), son los niveles de ruido asociados a ese depósito térmico por debajo o por encima del umbral para una simulación eficiente con la clásica recursos? Si es esto último, ¿qué algoritmos de simulación son óptimos?

$k$$k$$k$

$f(k)$$k$$f(k)$$2^k$$k$$1 \le f(k) < 2^k$

$k$$n$$k$$f(k)/2^k$

$f(k)$$f(k)+1$

• Jan Kratochvíl, Petr Savický y Zsolt Tuza, Una ocurrencia más de variables hace que la satisfacción salte de trivial a NP-completo , SIAM J. Comput. 22 (1) 203–210, 1993. doi: 10.1137 / 0222015

$f(k)$$f(k) = \Theta(2^k/k)$

• Heidi Gebauer, Prueba de la conjetura del vecindario con implicaciones para SAT , Combinatorica 32 (5) 573–587, 2012. doi: 10.1007 / s00493-012-2679-y (preprint)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, el lema local es ajustado para SAT , SODA 2011.