Sagen wir, wir sind gegeben Sätze und die Größe ihrer Vereinigung ist . Wir möchten eine kleine Menge konstruieren, die mindestens enthält des gegebene Sätze.
Nehmen wir das an ist weniger als ein Polynom in dh: . In diesem Fall gibt es einen effizienten (Polynom-) Algorithmus für das Optimierungsproblem:
Finden Sie den kleinsten Satz, der mindestens enthält des gegebene Sätze.
Antworten:
Das Problem ist NP-vollständig. Hier ist eine Reduktion von 3SAT-5, einer NP-vollständigen Version von 3SAT, in der jede Variable genau fünfmal vorkommt (und daher die Anzahl der Variablen und die Anzahl der Klauseln linear zusammenhängen).
Wir beginnen mit dem Aufbau von zwei Mengen-Systemen. Das erste SystemS besteht aus 6 Sätzen A0,A1,B0,B1,C0,C1 und 15 Elemente D={0,1}4∖(1,1,1,1) und hat die folgende Eigenschaft:
Das zweite SystemT besteht aus 2n setzt X1,Y1,…,Xn,Yn und O(n2) Elemente und hat die folgende Eigenschaft. Rufen Sie eine Familie vonn setzt aus T richtig, wenn es genau eines von jedem enthältXi,Yi . Alle richtigen Familien vonn Sets decken die gleiche Anzahl von Elementen ab M und jede unangemessene Familie von n Sets deckt mindestens ab M+1 Elemente.
Die Menge der Elemente besteht aus allen ungeordneten Paaren von Mengen{S,T} andere als die der Form {Xi,Yi} . Jedes SetS∈T besteht aus allen 2n−2 Paare, die es enthalten. LassenF eine Familie von sein n Sets, mit Ergänzung F¯¯¯¯ . Die einzigen Elemente, die nicht von abgedeckt werdenF sind die der Form {S,T} wo S,T∈F¯¯¯¯ . WennF ist dann richtig so ist F¯¯¯¯ und so gibt es Elemente, die nicht behandelt werden. Wenn korrekt ist, gilt dies auch für , sodass weniger als Elemente nicht behandelt werden.(n2) F F¯¯¯¯ (n2)
Die Reduzierung. Sei eine Instanz von 3SAT-5 mit Variablen und Klauseln. Für jede Klausel gibt es eine Kopie von system . Es gibt auch eine Kopie von in der jedes Element durch Elemente ersetzt wird. Die Gesamtzahl der Elemente ist in polynomisch .ϕ n m=5n/3 ϕj Sj S T~ T N=13m+1 n
Für jede Variable gibt es zwei Mengen und . Die Menge ist die Vereinigung der folgenden sechs Mengen:xi X0i X1i X0i
Die Menge ist ähnlich definiert als die Vereinigung der folgenden sechs Mengen:X1i
Das Problem besteht darin, zu entscheiden, ob es Mengen gibt, die zusammen Elemente (oder weniger) abdecken .n 13m+NM
Wenn erfüllt werden kann, sagen wir mit der Wahrheitszuweisung , dann deckt genau Elemente ab. Nehmen wir umgekehrt an, es gibt eine Möglichkeit, höchstens Elemente abzudecken . Wenn die Lösung nicht korrekt ist, deckt sie mindestens Elemente ab (wobei nur berücksichtigt wird ). Wenn es richtig ist, entspricht es einer Wahrheitszuweisung , und es ist leicht zu überprüfen, ob die Anzahl der abgedeckten Elemente beträgt , wobei die Anzahl der gefälschten Klauseln ist. Daher ist und wir schließen daraus, dassϕ xi {Xxii:1≤i≤n} 13m+NM 13m+NM N(M+1)>13m+NM T~ xi 13m+NM+Z Z Z=0 xi ist eine befriedigende Aufgabe.
quelle