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

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 .$x_1,\ldots,x_n$$f(x_1,\ldots,x_n) = \bigwedge C_i$$C_i$$x_1,\ldots,x_n$$i$$1$$m$

Zum Beispiel ist eine monotone CNF-Formel mit 2 Termen auf 4 Variablen.$(x_1 \vee x_3 \vee x_4) \wedge (x_2 \vee x_4)$

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(n^2)$$o(n^2)$

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 = (x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge \ldots \wedge (x_1 \vee x_n)$$x_1 \vee (x_2 \wedge x_3 \wedge \ldots \wedge x_n)$

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 . $\Omega(n^2/\log n)$$exp(n^2)$ $n$$n$$exp(s \log s)$$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 .$\log n$$O(n^2/\log n)$

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.$F$$F$$F$

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) .$n$$f$$n$