Random 3-SAT: Quelle est la plage expérimentale consensuelle du seuil?

Le rapport critique des clauses aux variables pour le 3-SAT aléatoire est supérieur à 3 et inférieur à 6, et semble être communément décrit comme «autour de 4,2» ou «autour de 4,25». Mezard, Parisi et Zecchina prouvent (au sens physique) que le rapport critique est 4.256, tandis que les premier et troisième auteurs prouvent qu'il est 4.267.

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

La motivation pour moi de poser cette question est que si le rapport pouvait être , puis la réduction standard de 3-SAT en NAE-3-SAT (transformation declauses etvariables enclauses etvariables) donne un ratio de, ce qui semble peu probable mais serait plutôt joli cool. $2+\sqrt{5} \approx 4.236$ $m$ $n$ $2m$ $m+n+1$ $\phi$

sat phase-transition random-k-sat Andrew D. King
la source

Vous devez définir ce que signifie qu'un ratio soit critique.

Tyson Williams

α

$\alpha$

< α n

$< \alpha n$

> α n

$> \alpha n$

1

$1$

n \to \infty

$n \to \infty$

doublon possible de Quelles sont les limites supérieures et inférieures actuellement les plus connues sur le seuil de (non) satisfiabilité pour k-sat et / ou 3-sat aléatoire?

András Salamon

Je soutiens que la question est distincte. Je cherche une estimation de l'ensemble de valeurs qui, par exemple, ne choquerait aucun expert de la communauté. Je ne pense pas que quoi que ce soit en dessous de 4, par exemple, se qualifie. (Je me rends compte que cela est, dans une certaine mesure, soumis au kilométrage individuel.)

Andrew D. King

Réponses:

À la lumière de la vérification Ding - Sly - Sun de l'image de rupture de symétrie de réplique en 1 étape pour kSAT (lorsque k est suffisamment grand), je pense que les experts seraient maintenant assez surpris si la formule conjecturée MPZ / MMZ pour la satisfiabilité 3SAT seuil (valeur approximative: 4,2667) est incorrect.

Ryan O'Donnell
la source

Je pense que c'est le document mentionné dans cette réponse, par Jian Ding, Allan Sly et Nike Sun (118 pages!).

Discours du