Ist XOR-SAT NP-hart gewichtet?

7

Gegeben sind boolesche Variablen von denen jeweils positive Kosten und eine boolesche Funktion für diese in der Form ( bezeichnet XOR) mit , ganze Zahlen und für alle , , besteht das Problem darin, eine Zuordnung der Mindestkosten für , die erfülltnx1,,xnc1,,cnZ>0f

f(x1,,xn)=i=1kj=1lixrij
kZ>01lin1ri1<<rilini=1,,kj=1,,lix1,,xnf, wenn eine solche Zuordnung besteht. Die Kosten einer Zuweisung werden einfach durch
i{1,,n}xitrueci.
Ist dieses Problem NP-schwer, das heißt, ist das begleitende Entscheidungsproblem "Gibt es eine zufriedenstellende Kostenverteilung höchstens einen Wert K " NP-schwer?

Das Standard-XOR-SAT-Problem ist nun in P, da es direkt auf die Frage der Lösbarkeit eines linearen Gleichungssystems über F2 (siehe z. B. https://en.wikipedia.org/wiki) / Boolean_satisfiability_problem # XOR-Befriedigung ). Das Ergebnis dieser Lösung (falls vorhanden) ist ein affiner Unterraum von F2n . Das Problem wird somit reduziert, um das Element auszuwählen, das mit minimalen Kosten aus diesem Unterraum entspricht. Leider kann dieser Unterraum ziemlich groß sein und tatsächlich f in binärer k×n Matrixform umschreiben , mit einer 1 für jedes xrij in der i ten Zeile und dem rij-te Spalte und andernfalls Null erhalten wir ein Kostenminimierungsproblem, das Ax = 1 unterliegt ,

Ax=1,
wobei A Matrix ist, x der Spaltenvektor ist, der aus x1,,xn und 1 der All-1-Vektor ist. Dies ist ein Beispiel für ein binäres lineares Programmierproblem, von dem bekannt ist, dass es im Allgemeinen NP-hart ist. Die Frage ist also, ist es auch in diesem speziellen Fall NP-schwer?
Alexander Klauer
quelle

Antworten:

9

Ein klassisches Ergebnis von Berlekamp, ​​McEliece und van Tilborg zeigt, dass das folgende Problem, die Dekodierung mit maximaler Wahrscheinlichkeit, NP-vollständig ist: Bestimmen Sie, ob eine Matrix und ein Vektor über und eine ganze Zahl vorhanden sind ist eine Lösung für mit höchstens Hamming-Gewicht .AbF2wAx=bw

Sie können dieses Problem auf Ihr Problem reduzieren. Das System entspricht der Konjunktion von Gleichungen der Form . Wenn , hat diese Gleichung bereits die richtige Form. Wenn ist, XOR wir eine zusätzliche Variable auf der rechten Seite XOR und erzwingen dann, dass diese Variable indem wir eine zusätzliche Gleichung hinzufügen . Wir definieren die Gewichte wie folgt: hat das Gewicht und hat das GewichtAx=bxi1xim=ββ=1β=0y1y=1y0x11. Wir haben jetzt eine äquivalente Formulierung der Maximum-Likelihood-Decodierung erreicht, die ein Beispiel für Ihr Problem ist.

Yuval Filmus
quelle