Maxsat mit DPLL-Algorithmus?

Question

Es ist möglich, von einem DPLL-Algorithmus M als maximal für maximales Problem zurückzukehren ?:

Ich habe ein Beispiel:

https://en.wikipedia.org/wiki/dpll_algorithmus

Answer 1

Der DPLL-Algorithmus versucht nicht, so viele Klauseln wie möglich zu befriedigen.Wenn es eine zufriedenstellende Aufgabe gibt, wird DPLL es finden.Andernfalls versucht DPLL eine Reihe von Teilzuweisungen, bis es außerhalb der Möglichkeiten läuft, und dann wird die Formel nicht erklar erde.Im Falle einer unatisiatierbaren Formel gibt es jedoch keine Garantie, dass DPLL die maximale Anzahl ergiebiger Klauseln auf dem Weg zur Nachweis der Unzufriedenheit erkennen wird.

Das MAXSAT-Problem ist im Zusammenhang mit der Suche nach den minimal unzufriedenen Unterformulas (Musen) einer Instanz.Bestimmen, ob ein Satz von Klauseln ein Mus ist, ist ein dp-vollständige Problem.Es wird erwartet, dass dies schwieriger ist als bloße NP-Vollständigkeit, daher ist es unwahrscheinlich, dass das Modifizieren von DPLL, um Teillösungen zurückzugeben, fruchtbar ist.Da die Klasse DP in $ \ DELTA ^ P_2 $ enthalten ist, können Sie ein Schema einstellen, das DPLL (oder zugehörige Algorithmen) eine Polynomanzahl von MAXSAT anruft, um einen MAXSat herzustellenErgebnis.