Reduzieren Sie das folgende Problem auf SAT

21

Hier liegt das Problem. Gegeben sei , wobei jedes T i{ 1 , , n } ist . Gibt es eine Teilmenge S { 1 , ... , n } mit einer Größe von höchstens k , so dass S T i & ne; für alle i ? Ich versuche, dieses Problem auf SAT zu reduzieren. Meine Idee einer Lösung wäre, eine Variable x i zu habenk,n,T1,,TmTi{1,,n}S{1,,n}kSTiixifür jede von 1 bis . Für jedes T i , erstellen Sie eine Klausel ( x i 1x i k ) wenn T i = { i 1 , ... , i k } . Dann und all diese Klauseln zusammen. Dies ist jedoch eindeutig keine vollständige Lösung, da es nicht die Beschränkung darstellt, die S höchstens k Elemente haben muss. Ich weiß, dass ich mehr Variablen erstellen muss, aber ich bin mir einfach nicht sicher, wie. Ich habe also zwei Fragen:nTi(xi1xik)Ti={i1,,ik}Sk

  1. Ist meine Lösungsidee auf dem richtigen Weg?
  2. Wie sollen die neuen Variablen erstellt werden, damit sie zur Darstellung der Kardinalitätsbeschränkung ?k
Aden Dong
quelle
5
Nur eine Bemerkung: Ihr Problem ist als HITTING SET bekannt , eine äquivalente Formulierung des SET COVER- Problems.
A.Schulz

Antworten:

13

Es sieht so aus, als würden Sie versuchen, eine Hypergraph-Transversale der Größe zu berechnen . Das heißt, { T 1 , , T m } ist Ihr Hypergraph und S ist Ihr Transversal. Eine Standardübersetzung besteht darin, die Klauseln so auszudrücken, wie Sie sie haben, und dann die Längenbeschränkung in eine Kardinalitätsbedingung zu übersetzen.k{T1,,Tm}S

So nutzen Sie Ihre bestehende Codierung, dh und dann Klauseln hinzufügen kodieren Σ 1 i n x ik .1jmiTjxi1inxik

ist ein Kardinalität constraint. Es gibt verschiedene Übersetzungen von Kardinalitätsbeschränkungen in SAT.1inxik

Die einfachste, aber ziemlich große Kardinalitätsbeschränkungsübersetzung ist nur . Auf diese Weise repräsentiert jede Disjunktion die Bedingung ¬ i X x i - für alle Teilmengen X von { 1 , , n }X{1,,n},|X|=k+1iX¬xi¬iXxiX{1,,n}der Größe k + 1. Das heißt, wir stellen sicher, dass auf keinen Fall mehr als k Variablen festgelegt werden können. Beachten Sie, dass dies keine Polynomgröße in k

Einige Links zu Artikeln über platzsparendere Kardinalitätsbeschränkungsübersetzungen mit Polynomgröße in k :

Wenn Sie tatsächlich an der Lösung solcher Probleme interessiert sind, ist es vielleicht besser, sie als pseudo-boolesche Probleme zu formulieren (siehe Wiki-Artikel über pseudo-boolesche Probleme ) und pseudo-boolesche Löser zu verwenden (siehe pseudo-boolesche Konkurrenz ). Auf diese Weise sind die Kardinalitätsbedingungen nur pseudo-boolesche Bedingungen und Teil der Sprache - hoffentlich behandelt der pseudo-boolesche Löser sie dann direkt und damit effizienter.

MGwynne
quelle
1
Bitte beschreiben Sie alle Links kurz (mindestens Autor und Titel), damit die Leute die Dokumente finden können, falls die Links brechen. Es ist wahrscheinlich am besten, DOI zu verwenden, falls verfügbar.
Raphael
1
@ Raffael Guter Punkt! Entschuldigung, ich hätte das von Anfang an tun sollen. Ich habe jetzt alle Links aktualisiert. Ich bin nicht sicher, ob Springer DOIs bereitstellt, aber es sollte jetzt genügend Informationen geben, um sie zu finden, wenn die Links nicht funktionieren. Hinweis: Ich verweise nicht auf die offiziellen PDF-Dateien von Springer, um Zugriffsprobleme zu vermeiden.
MGwynne
Aber es scheint, dass die Reduktion, die Sie gaben, nicht in Polynomzeit ist, nicht wahr?
Aden Dong
kkk
MGwynne, ich neige dazu, das offizielle DOI immer zu verlinken, auch wenn es kostenpflichtig ist, um zukunftssicher zu sein, und zusätzlich kostenlose Versionen. Aber so wie es jetzt ist, sollte jeder in der Lage sein, die Papiere zu finden, also ist es vollkommen in Ordnung.
Raphael
6

k

Γ2,1+Γ2,1+ist die Klasse aller positiven CNF-Formeln. In diesem Fall müssten Sie sich überlegen, welche Parametrierung in Ihrem Fall sinnvoll wäre.

Ich gehe davon aus, dass Sie nach einer expliziten Reduktion suchen, aber wenn nicht, können Sie jederzeit auf das Cook-Levin-Theorem zurückgreifen .

Luke Mathieson
quelle