Referencia Preguntando: Transición de fase en SAT

Question

Esta no es una pregunta técnica, espero que esta comunidad tenga una habitación para tales preguntas, pero lo eliminaré en caso de que esto sea inapropiado.

Se ha observado experimentalmente (por ejemplo, aquí ) que al elegir un $ 3 $ -sat fórmula por el siguiente proceso:

en la entrada $ (n, \ alfa n) $ : Elija $ \ alfa n $ cláusulas uniformemente al azar del conjunto de todas las cláusulas de $ 3 $ literales sobre $ x_1, \ ldots, x_n $ y devuelve la conjunción de estas cláusulas.

La probabilidad de que la fórmula de salida sea satisfactoria depende de $ \ alfa $ : si $ \ alfa \ ll C $ La probabilidad está muy cerca de $ 1 $ , y si $ \ alfa \ gg c $ La probabilidad está muy cerca de $ 0 $ (se ha observado para un general $ k $ -sat instances ).

Mi pregunta es ¿cuál es la comprensión teórica de este problema? A lo mejor de mi conocimiento, para otros problemas, es posible probar reclamaciones similares con bastante facilidad (por ejemplo, la probabilidad de que un gráfico aleatorio $ g (n, p) $ tiene Una clique de tamaño $ 4 $ es casi $ 1 $ cuando $ P (n)=onga (n ^ {- 2/3}) $ y es casi $ 0 $ cuando $ P (n)= O (n ^ {- 2/3}) $ , y puede ser probado por un uso básico de segundo momentos).

Sin embargo, para SAT no pude encontrar pruebas. ¿Conoces algún progreso en este problema?

Answer 1

Los dos rigurosos resultados más relevantes son:

1. ehud friedgut, umbrales nítidos de propiedades del gráfico, y el $ k $ -sat problem . Este documento (con un apéndice de Jean Bourgain) muestra que $ k $ -sat exhibe un umbral agudo. Sin embargo, a priori este umbral podría depender de $ n $ (es decir, este método no puede mostrar que $ \ alfa $ es constante).
2. JIAN DING, ALLAN SLY, NIKE SUN, PRUEBA DE LA CONYECCIÓN DE LA CONQUIBILIDAD PARA LARGE $ K $ . Los autores determinan el valor exacto de $ \ alfa $ para $ k \ geq k_0 $ . Este valor de $ \ alfa $ ha sido calculado por los físicos utilizando el método de cavidad, pero sus argumentos no son rigurosos.

El trabajo relacionado discute la geometría del espacio de la solución de $ k $ -sat alrededor de varios umbrales. Vea, por ejemplo, Dimitris Achlioptas, Amin Coxa-Oghlan, Federico Ricci-Tersenghi, en el Geometría de espacio de solución de problemas de satisfacción de restricción aleatoria .