Tautologien / Widersprüche im Durchschnitt jenseits des zufälligen k-CNF-Modells

16

Es ist bekannt, dass zufällige CNF-Formeln über Variablen mit Klauseln mit hoher Wahrscheinlichkeit für eine ausreichend große Konstante erfüllt werden können (dh sie sind Widersprüche) . Zufällige CNF-Formeln (für groß genug) bilden somit eine natürliche Verteilung über nicht erfüllbare Boolesche Formeln (oder zweifach über Tautologien, dh Negationen von Widersprüchen). Diese Verteilung wurde eingehend untersucht.n c n c k ckncnckc

Meine Frage ist folgende : Gibt es irgendwelche anderen etablierten Verteilungen über Aussagen-Tautologien oder Widersprüche, die als Erfassung des "Durchschnittsfalls" von Tautologien oder unbefriedigbaren Formeln angesehen werden können? Wurden diese Verteilungen intensiv untersucht?

cc.complexity-theory reference-request lo.logic sat random-k-sat Iddo Tzameret
quelle
1
@Iddo Tautologien gibt es in einem "echten" CNF-Modell nicht, da Sie sonst ein Literal und dessen Ergänzung in derselben Klausel benötigen würden. Tautologien sind für das Studium in CNF nicht interessant.
Tayfun Pay
1
@Pay, die Negation einer unbefriedigenden Formel ist offensichtlich eine Tautologie. Daher können wir zufällige k-CNFs als Verteilung über Tautologien betrachten (wenn das Verhältnis von Klausel zu Variable groß genug ist und eine Wahrscheinlichkeit von o (1) besteht, dass ein k-CNF erfüllt werden kann).
Iddo Tzameret
1
Ich denke, dass Tayfun Recht hat. Sie sollten entweder davon sprechen, dass CNF-Formeln nicht befriedigend sind, oder dass DNF-Formeln Tautologien sind. In der aktuellen Frage mischen Sie die beiden.
Tsuyoshi Ito
1
Dies ist meine letzte Bemerkung zu diesem Thema: Ich weiß nicht, warum Sie darauf bestehen, das Wort "Tautologien" beizubehalten, was eindeutig falsch ist, wie Tayfun erklärte. Aber es geht mir gut, wenn Sie nicht die Kommentare anderer einbeziehen möchten, um den Wortlaut Ihrer Frage zu verbessern.
Tsuyoshi Ito
3
Ich bevorzuge es, den Begriff "Tautologien" im Titel zu belassen, da ich nach Verteilungen von Tautologien oder Widersprüchen frage und die Frage entsprechend formuliert ist.
Iddo Tzameret

Antworten:

4

Paul Beame hat zwei Arbeiten (mit verschiedenen Koautoren), in denen die Auflösungskomplexität bestimmter Verteilungen von Zufallsformeln untersucht wird. Diese Formeln entstehen, indem Eigenschaften wie k-Färbbarkeit oder unabhängige Mengen der Größe k von Zufallsgraphen aus der üblichen Verteilung . Hier sind die Links:G(n,p)

Paul Beame, Russell Impagliazzo und Ashish Sabharwal. Die Auflösungskomplexität unabhängiger Mengen und Scheitelpunkte wird in zufälligen Diagrammen dargestellt. Computational Complexity, 16 (3): 245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell und Cristopher Moore. Die Auflösungskomplexität der k-Färbbarkeit von Zufallsgraphen. Discrete Applied Mathematics, 153: 25–47, 2005.

Jan Johannsen
quelle