Aufgabe, die Formel unbefriedigend zu machen

8

Lässt sich vorstellen , wir eine erfüllbare Formel Das Problem „zu lösen , ist Gibt es eine Zuweisung für Variablen was macht F unbefriedigend? ". Eine Möglichkeit zum Lösen besteht darin, alle Lösungen für F in Form von Variablen $F(A_0, A_1,...A_k,S_0,...,S_n)$ $(S_0,...,S_n)$ und wenn die Anzahl < , ist die fehlende Lösung die Antwort, aber die Komplexität dieses Algorithmus ist groß, wenn die Anzahl solcher Zuweisungen gering ist. $S_0,...,S_n$ $2^n$

Meine Fragen sind:

Gibt es eine Möglichkeit, das Problem mit weniger SAT-Solver-Aufrufen zu lösen?
Ist es theoretisch ein bekanntes Problem (Was sollte ich googeln, um darüber zu lesen)?

logic satisfiability sat-solvers Grigor Aghanyan
quelle

1

"was F unbefriedigend macht" - das macht keinen Sinn. Meinst du einfach "befriedigt F nicht"? Dann sprechen Sie über das Problem TAUTOLOGY (bzw. dessen Ergänzung).

Raphael

Wenn Sie die Tatsache ignorieren, dass die Frage keinen Sinn ergibt, denke ich, dass der Versuch, eine Lösung für

zu finden, das sein könnte, wonach Sie suchen.

\neg F (A_{0}, A_{1}, \dots, A_{k}, S_{0}, \dots, S_{n})

$\neg F(A_0,A_1,\ldots, A_k,S_0,\ldots, S_n)$

Dave Clarke

Vielleicht war ich nicht klar. Nach der Anwendung Zuweisungen für

werden wir eine andere Formel

und diese unerfüllbar sein muss.

(S_{0}, . . ., S_{n})

$(S_0,...,S_n)$

G (A_{0}, . . ., A_{k})

$G(A_0 ,..., A_k)$

Grigor Aghanyan

6

Ihr Problem ist das kanonische -vollständige Problem: Als solches wird angenommen, dass es schwieriger ist als SAT (was ). Das Lösen mit ein paar SAT-Orakel-Aufrufen ist vergleichbar mit dem effizienten Lösen von SAT selbst (die P vs. NP-Frage), obwohl es sein könnte, dass während $\Sigma_2^P$

\exists \vec{S.} \forall \vec{EIN} \neg F. (\vec{EIN}, \vec{S.}) .

$\exists \vec{S} \forall \vec{A} \lnot F(\vec{A},\vec{S}).$

Σ_{1}^{P}

$\Sigma_1^P$

Σ_{2}^{P} = Σ_{1}^{P}

$\Sigma_2^P = \Sigma_1^P$

P \neq N P

$P \neq NP$ In gewissem Sinne gibt es also mehr Hoffnung für Ihr Problem als für SAT selbst.

Yuval Filmus
quelle

Genau. Danke für die Antwort. Die Lösung mit

Solver-Aufrufen ist also "keine schlechte Lösung" dafür? Ein Link für Artikel zu diesem Problem wird mir sehr helfen.

2^{n}

$2^n$

Grigor Aghanyan

Σ_{2}^{P}

$\Sigma_2^P$

4

Dies ist ein bekanntes Problem: Es ist das 2QBF-Problem. Leider ist es deutlich schwieriger als SAT. Es sind QBF-Löser verfügbar. Sie könnten versuchen, einen QBF-Löser (oder noch besser einen 2QBF-Löser) zu finden und zu prüfen, ob er Ihre Formel lösen kann. QBF-Löser skalieren jedoch nicht so gut wie SAT-Löser. QBF ist deutlich schwieriger als SAT.

Unter https://cstheory.stackexchange.com/q/11022/5038 und http://www.qbflib.org/ finden Sie einige Ressourcen, die hilfreich sein könnten.

DW
quelle

Aufgabe, die Formel unbefriedigend zu machen

Antworten: