Algorithmus für idempotent algebra
-
28-09-2020 - |
Frage
Eine boolesche Algebra-Expression kann mit einem idempotent algebra mitgeteilt werden
wobei $ \ otimes $ das idempotent-Produkt (keine Befugnisse) ist. Beispielsweise, $$ (A + B) \ OTIMES (A-B)= A -AB + AB - B= A-B. $$
die CNF-Formel
$$ \ phi= (a \ vee b) \; (b \ vee c) (b \ vee \ bar c) (\ bar b \ vee \ bar c) \; (a \ vee c) (\ bar a \ vee \ bar c) $$ $$
kann in das, was ich den idempotent-Ausdruck anrufen würde, umgewandelt werden kann
Dieser Ausdruck wird erweitert, um
Frage 1: Was ist die Komplexität dieser Aufgabe? Wie hoch in der Polynomhierarchie ist es?
Zweitens, gegeben eines anderen idempotenten Ausdrucks $$ \ phi= AC + AD + BC + BD-ABC-ABD-2ACD-2BCD + 2ABCD, $$ < / p>
Ich bin daran interessiert, über die Bedingungen mit gleicher Homogenität zu summieren. Indem Sie alle Variablen
Frage 2: Was ist die Komplexität des Berechnens des Homogenitätsvektors, da er einen idempotenten Ausdruck als Input gegeben hat? Wie hoch in der Polynomhierarchie ist es?
Lösung
Lassen Sie uns die folgende Entscheidungsversion Ihres ersten Problems in Betracht ziehen:
Angesichts einer SAT-Instanz hat seine multilineare Darstellung in den meisten
$ D $ ?
Ich behaupte, dass dies der Fall ist, wenn die SAT-Instanz eine erfüllende Zuordnung mit höchstens $ D $ hat.
In der Tat können Sie zunächst angenommen werden, dass $ M $ ein inklusionsminimaler Begriff in der multilinearen Darstellung der Instanz ist. Ersetzen 1 für die Variablen in $ M $ und 0 für die Variablen außerhalb von $ M $ , wir bekommen 1, das heißt, dass die Instanz erfüllt ist. Dies zeigt, dass, wenn die multilineare Darstellung in den meisten
nun angenommen, dass alle Begriffe in der multilinearen Darstellung mehr als $ D $ haben. Wenn wir einen Auftrag mit höchstens $ D $ ersetzen, dann alle Monomialen gleich 0, und so fälscht die Zuweisung die Instanz.
Daher entspricht die Entscheidungsversion der minimalen SAT-SAT, was folgendes Problem ist:
Angesichts einer SAT-Instanz hat es eine erfüllende Aufgabe mit höchstens $ D $ one?
Das Problem ist in NP (es ist einfach, die Anzahl derjenigen in einer erfüllenden Zuordnung zu zählen), und es ist eindeutig NP-HARD (Take $ d= n $ ). Daher ist das Problem np-komplett.
Mit einem NP-Oracle können wir leicht ein Monom mit minimalem Grad finden, äquivalent, einer erfüllenden Zuordnung mit den geringsten. Ersetzen Sie einfach ein 0 in einem der Variablen, und sehen Sie, ob er das minimale Gewicht einer Lösung erhöht. Wenn dies der Fall ist, setzen Sie diese Variable auf 1 ein, sonst auf Null einstellen und zur nächsten Variablen fortfahren. Dies beantwortet Ihre erste Frage.