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

14

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 demclauses etnvariables en2mclauses etm+n+1variables) donne un ratio deϕ, ce qui semble peu probable mais serait plutôt joli cool.2+54.236mn2mm+n+1ϕ

Andrew D. King
la source
1
Vous devez définir ce que signifie qu'un ratio soit critique.
Tyson Williams
3
α<αn>αn1n
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:

9

À 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
1
Je pense que c'est le document mentionné dans cette réponse, par Jian Ding, Allan Sly et Nike Sun (118 pages!).
Discours du