Référence Position: Transition de phase en SAT

Question

Ce n'est pas une question technique, j'espère que cette communauté dispose d'une place à de telles questions, mais je vais la supprimer au cas où cela ne serait pas inapproprié.

Il a été observé expérimentalement (par exemple, Ici ) que lors du choix d'un $ 3 $ -Sat formule par le processus suivant:

sur l'entrée $ (n, \ alpha n) $ : choisissez $ \ alpha n $ clauses Uniformément au hasard de l'ensemble de toutes les clauses de $ 3 $ littéraux sur $ x_1, \ ldots, x_n $ et renvoyez la conjonction de ces clauses.

La probabilité que la formule sortie est satisfaite dépend de $ \ alpha $ : si $ \ alpha \ ll c $ La probabilité est très proche de 1 $ , et si $ \ alpha \ gg $ La probabilité est très proche de 0 $ (il a été observé pour un général $ k $ -sat instances ).

Ma question est de savoir quelle est la compréhension théorique de ce problème? Au mieux de mes connaissances, pour d'autres problèmes, il est possible de prouver des revendications similaires (par exemple, la probabilité qu'un graphe aléatoire $ g (n, p) $ a Une clique de taille 4 $ est presque $ 1 $ quand $ P (n)=oméga (n ^ {- 2/3}) $ et est presque $ 0 $ quand $ p (n)= o (n ^ {- 2/3}) $ , et il peut être prouvé par une utilisation fondamentale de second moments).

Cependant, pour SAT, je ne pouvais pas trouver des preuves. Connaissez-vous des progrès dans ce problème?

Answer 1

Les deux résultats rigoureux les plus pertinents sont:

1. Ehud Friedgut, seuils pointus de propriétés de graphique, et la $ K $ -sat problème . Ce papier (avec une annexe de Jean Bourgain) montre que $ k $ -Sat présente un seuil tranchant. Cependant, a priori Ce seuil pourrait dépendre de $ n $ (c.-à-d., Cette méthode ne peut pas montrer que $ \ alpha $ est constant).
2. Jian Ding, Allan Sly, Nike Sun, Preuve de la conjecture de satisfaction pour la grande classe $ K $ . Les auteurs déterminent la valeur exacte de $ \ alpha $ pour $ k \ geq k_0 $ . Cette valeur de $ \ alpha $ avait été calculée par des physiciens à l'aide de la méthode de la cavité, mais leurs arguments ne sont pas rigoureux.

Le travail connexe aborde la géométrie de l'espace de solution de $ k $ -sat autour de divers seuils. Voir par exemple Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, sur le Géométrie de l'espace de solution de problèmes de satisfaction de contrainte aléatoire .