Combien de tautologies existe-t-il?

Étant donné , combien de -DNF avec variables et clauses sont tautologiques? (ou combien de -CNF ne sont pas satisfaisants?)k n m $m, n, k$$k$$n$$m$$k$

La réponse dépend de , m et n . Les nombres exacts ne sont généralement pas connus, mais il existe un phénomène de "seuil" qui, pour la plupart des paramètres de k , m , n , soit presque toutes les instances k -SAT sont satisfaisables, soit presque toutes les instances ne sont pas satisfaisantes. Par exemple, lorsque k = 3 , il a été empiriquement observé que lorsque m < 4,27 n , toutes sauf une o ( 1 ) fraction d'instances 3-SAT sont satisfaisables, et lorsque m > 4,27 n , toutes sauf a $k$$m$$n$$k$$m$$n$$k$$k=3$$m < 4.27 n$$o(1)$$m > 4.27n$ fraction n'est pas satisfaisante. (Il existe également des preuves de limites rigoureuses.)$o(1)$

Un point de départ est "L'ordre asymptotique du seuil k-SAT" .

Amin Coja-Oghlan a également beaucoup travaillé sur ces problèmes de seuil de satisfiabilité.

Il s'agit d'un commentaire étendu pour compléter la réponse de Ryan, qui traite des seuils où le nombre de clauses devient suffisamment important pour que l'instance soit presque sûrement insatisfaisante. On peut également calculer les seuils beaucoup plus grands où le nombre de clauses force l' insatisfiabilité quand il dépasse une fonction de .$n$

Notez que certains problèmes techniques doivent être résolus. Si les clauses répétées sont comptées en , alors m peut être rendu aussi grand que souhaité sans changer n . Cela détruirait la plupart des relations entre m et n . Supposons donc que m est le nombre de clauses distinctes. Nous devons décider d'un autre détail, si les instances sont codées de sorte que l'ordre des littéraux dans une clause ou l'ordre des clauses dans une instance soit important. Supposons que cela ne soit pas important, donc deux instances sont considérées comme équivalentes si elles contiennent les mêmes clauses, et deux clauses sont équivalentes si elles contiennent les mêmes littéraux. Avec ces hypothèses, nous pouvons maintenant limiter le nombre de clauses distinctes qui peuvent être exprimées avec$m$$m$$n$$m$$n$$m$ variables. Chaque clause peut avoir chaque variable se produisant positivement ou négativement, ou pas du tout, puis m ≤ 3 n .$n$$m\le 3^n$

Considérons d'abord SAT sans restriction sur . Quel est le plus grand m tel que l'instance soit satisfiable? Sans perte de généralité, nous pouvons supposer que l'affectation tout à zéro est une solution. Il existe alors 3 n - 2 n clauses différentes cohérentes avec cette solution, chacune contenant au moins un littéral nié. D'où m ≤ 3 n - 2 n pour toute instance satisfaisable. L'instance composée de toutes les clauses qui contiennent chacune au moins un littéral négatif a ce nombre de clauses et est satisfaite par l'affectation tout à zéro. En outre, par le principe du pigeonhole toute instance avec au moins 3 $k$$m$$3^n-2^n$$m\le 3^n-2^n$ clauses n + 1 ne sont pas satisfaisantes.$3^n-2^n+1$

Cela donne sous-ensembles différents de telles clauses, chacune représentant une instance distincte qui est satisfaite par une affectation. En comparaison, le nombre total d'instances différentes est de 2 3 n .$2^{3^n-2^n}$$2^{3^n}$

Maintenant, en modifiant ce qui précède pour les instances dans lesquelles chaque clause a au plus littéraux, il y a ∑ k i = 0 ($k$distinguent ces clauses, et∑ k i = 0 ($\sum_{i=0}^k \binom{n}{i}2^i$ clauses dans lesquelles il n'y a pas de littéraux négatifs, doncm≤∑ k i = 0 ($\sum_{i=0}^k \binom{n}{i}$pour les cas satisfaisables, et toutmplus grandn'est pas satisfaisant. Il y a alors2∑ k i = 0 ($m\le \sum_{i=0}^k \binom{n}{i}(2^i - 1)$$m$instances satisfaites par une affectation particulière, sur un total de2∑ k i = 0 ($2^{\sum_{i=0}^k \binom{n}{i}(2^i - 1)}$kinstances -SAT.$2^{\sum_{i=0}^k \binom{n}{i}2^i}$ $k$