Kürzeste Formel für einen n-term monotonen CNF

10

Eine monotone CNF-Formel mit m Termen für n Variablen ( ) ist eine Formel der Form , wobei jedes ein ODER einer Teilmenge der Variablen ist und reichen von bis .x1,,xnf(x1,,xn)=CiCix1,,xni1m

Zum Beispiel ist eine monotone CNF-Formel mit 2 Termen auf 4 Variablen.(x1x3x4)(x2x4)

Ich suche nach der kürzesten Formel (nicht unbedingt monoton, nicht unbedingt CNF, jede Formel reicht aus!) Für denselben Variablensatz, der dieselbe Funktion wie eine bestimmte monotone CNF-Formel für n Variablen mit n Begriffen darstellt. (Beachten Sie, dass die Anzahl der Begriffe und Variablen gleich ist.)

Eine naheliegende Möglichkeit, eine Formel zu konstruieren, besteht darin, die gegebene CNF-Definition zu erweitern, wodurch wir eine Formel der Größe . (Definieren wir die Größe einer Formel als die Länge der Formel, wenn sie als Zeichenfolge geschrieben wird.) Ich möchte wissen, ob dies die effizienteste allgemeine Konstruktion ist oder ob für jeden monotonen n-Term-CNF eine Formel existiert der Größe .O(n2)o(n2)

Ich möchte nur wissen, ob dies möglich ist, ich bin nicht wirklich an einem Algorithmus interessiert. Wenn dies nicht möglich ist, wäre eine Funktion, die als Gegenbeispiel dient, großartig. Hinweise, auf die ich in der Literatur eine Antwort finden kann, sind ebenfalls willkommen.

EDIT: Ich füge ein Beispiel hinzu, um die Ausdünnung klarer zu machen.

Angenommen, die Eingabeformel lautet . Dies ist eine monotone CNF-Formel. Eine kürzere Formel, die dieselbe Funktion darstellt, lautet wie folgt: .f=(x1x2)(x1x3)(x1xn)x1(x2x3xn)

Robin Kothari
quelle

Antworten:

11

Sie können eine -Untergrenze mit einem Zählargument erhalten : Es gibt terminale CNFs für Variablen (dies ist einfach, erfordert jedoch nur ein wenig Sorgfalt sicher, dass es keine Überzählung gibt), aber es gibt Formeln (oder sogar Schaltungen) mit einer Größe von höchstens . Ω(n2/logn)exp(n2) nnexp(slogs)s

Es scheint, dass es schwierig sein wird, den letzten -Faktor zu gewinnen, da dafür eine quadratische Untergrenze der Formelgröße nachgewiesen werden müsste, und ich vermute, dass die wenigen vorhandenen Techniken dafür nicht ausreichen. kann sogar die richtige Antwort sein - zumindest für die Schaltungsgröße - unter Verwendung einer vierrussisch ähnlichen Technik .lognO(n2/logn)

Noam
quelle
Perfekt danke! Der log n-Faktor ist für mich nicht wirklich wichtig, daher beantwortet dies meine Frage vollständig.
Robin Kothari
2

Bedenken Sie, dass Sie für jeden CNF die Menge der Hauptimplikate berechnen können (von denen jedes Minimum eine Teilmenge sein muss), indem Sie den Abschluss unter Auflösung nehmen und die Eliminierung der Subsumtionen anwenden.

Im Fall eines monotonen CNF ist der Auflösungsschluss von jedoch (da keine negativen Literale vorhanden sind, ist keine Auflösung möglich). Daher ist der minimale CNF die Menge der Primzahlen, was genau die Formel ist, die Sie bereits haben.FFF

Natürlich gehe ich davon aus, dass Sie keine neuen Variablen einführen möchten.

Wenn Sie sicherstellen möchten, dass Sie eine Formel mit Begriffen haben, besteht die einzige Möglichkeit, dies zu erreichen, darin, einige der Klauseln durch Hinzufügen fehlender Variablen zu erweitern. Ein solcher CNF sollte für ein festes und die gleiche Anzahl von Literalen haben (das Größenmaß, das Sie meiner Meinung nach vorschlagen) .nfn

MGwynne
quelle
Schön, ich mag es. (Im Übrigen, falls der monotone DNF-Fall auftaucht, @Robin, glaube ich, dass dies interessant sein könnte: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )
Daniel Apon
1
Ich bin mir nicht sicher ob ich das verstehe. Die CNF-Mindestgröße ist möglicherweise die monotone CNF-Formel, die ich bereits habe, aber ich suche nach der kleinsten Längenformel aller Art. Es muss nicht CNF oder monoton sein. Ich werde meine Frage bearbeiten, um dies klarer zu machen.
Robin Kothari
1
Ah ich sehe. Nun, was ich gesagt habe, deckt ab, ob es CNF sein muss. Wenn es eine willkürliche Satzformel sein kann, muss ich mehr darüber nachdenken.
MGwynne