Random 3-SAT: ¿Cuál es el rango experimental de consenso del umbral?

La proporción crítica de cláusulas a variables para el 3-SAT aleatorio es más de 3 y menos de 6, y parece describirse comúnmente como "alrededor de 4.2" o "alrededor de 4.25". Mezard, Parisi y Zecchina prueban (en el sentido de la física) que la relación crítica es 4.256, mientras que el primer y tercer autores prueban que es 4.267.

What is the range of values that the critical ratio could possibly take?

La motivación para mí al hacer esta pregunta es que si la proporción pudiera ser , entonces la reducción estándar de 3-SAT a NAE-3-SAT (transformandocláusulas yvariables encláusulas ylas variables) da una proporción de, que parece poco probable pero sería bastante frio. $2+\sqrt{5} \approx 4.236$ $m$ $n$ $2m$ $m+n+1$ $\phi$

sat phase-transition random-k-sat Andrew D. King
fuente

Debe definir lo que significa que una relación sea crítica.

Tyson Williams

α

$\alpha$

< α n

$< \alpha n$

> α n

$> \alpha n$

1

$1$

n \to \infty

$n \to \infty$

posible duplicado de ¿Cuáles son los límites superior e inferior más conocidos actualmente en el umbral de (des) satisfacción para aleatorio k-sat y / o 3-sat?

András Salamon

Sostengo que la pregunta es distinta. Estoy buscando una estimación del conjunto de valores que, por ejemplo, no sorprendería a ningún experto en la comunidad. No creo que nada por debajo de 4, por ejemplo, califique. (Me doy cuenta de que esto está, hasta cierto punto, sujeto al kilometraje individual.)

Andrew D. King

Respuestas:

A la luz de la verificación Ding - Sly - Sun de la imagen de ruptura de simetría de réplica de 1 paso para kSAT (cuando k es lo suficientemente grande), creo que los expertos ahora estarían bastante sorprendidos si la fórmula conjeturada MPZ / MMZ para la satisfacción de 3SAT El umbral (valor aproximado: 4.2667) es incorrecto.

Ryan O'Donnell
fuente

Creo que este es el documento mencionado en esta respuesta, por Jian Ding, Allan Sly y Nike Sun (¡118 páginas!).

Moot