Tautologies / contradictions dans le cas moyen, au-delà du modèle aléatoire k-CNF

16

Il est bien connu que les formules aléatoires -CNF sur n variables avec c n clauses sont insatisfaisantes (c'est-à-dire qu'elles sont des contradictions) avec une probabilité élevée, pour une constante c suffisamment grande . Ainsi, les formules k -CNF aléatoires (pour c assez grand) constituent une distribution naturelle sur des formules booléennes insatisfaisantes (ou dualement sur des tautologies, c'est-à-dire des négations de contradictions). Cette distribution a été largement étudiée.kncnckc

Ma question est la suivante : existe-t-il d'autres distributions établies sur les tautologies ou contradictions propositionnelles, qui peuvent être considérées comme capturant le «cas moyen» des tautologies ou des formules insatisfaisantes? Ces distributions ont-elles été étudiées de manière approfondie?

cc.complexity-theory reference-request lo.logic sat random-k-sat Iddo Tzameret
la source
1
@Iddo Tautologies n'existe pas dans un "vrai" modèle CNF car sinon il faudrait avoir un littéral et son complément dans la même clause .... Les tautologies ne sont pas intéressantes à étudier en CNF.
Tayfun Payez
1
@Pay, la négation d'une formule insatisfaisante est évidemment une tautologie. Par conséquent, nous pouvons considérer les k-CNF aléatoires comme une distribution sur les tautologies (lorsque le rapport clause / variable est suffisamment grand et lorsqu'il existe une probabilité o (1) pour qu'un k-CNF soit satisfaisable).
Iddo Tzameret
1
Je pense que Tayfun a raison. Vous devriez parler de formules CNF insatisfaisantes ou de formules DNF de tautologies. Dans la question actuelle, vous mélangez les deux.
Tsuyoshi Ito
1
Voici mon dernier commentaire à ce sujet: je ne sais pas pourquoi vous insistez pour garder le mot «tautologies», ce qui est clairement faux, comme l'explique Tayfun. Mais je vais bien si vous ne voulez pas intégrer les commentaires des autres pour améliorer le libellé de votre question.
Tsuyoshi Ito
3
Je préfère garder le terme «tautologies» dans le titre parce que je pose des questions sur les distributions sur les tautologies ou les contradictions, et la question est formulée en conséquence.
Iddo Tzameret

Réponses:

4

Paul Beame a deux articles (avec divers co-auteurs) où la complexité de résolution de certaines distributions de formules aléatoires est étudiée. Ces formules résultent de l'expression de propriétés, telles que la colorabilité k ou la présence d'ensembles indépendants de taille k, de graphiques aléatoires à partir de la distribution habituelleg(n,p). Voici les liens:

Paul Beame, Russell Impagliazzo et Ashish Sabharwal. La complexité de résolution d'ensembles indépendants et de couvertures de sommets dans des graphiques aléatoires. Complexité informatique, 16 (3): 245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell et Cristopher Moore. La complexité de la résolution de la colorabilité aléatoire du graphique k. Discrete Applied Mathematics, 153: 25-47, 2005.

Jan Johannsen
la source