Algorithmus für idempotent algebra

Question

Eine boolesche Algebra-Expression kann mit einem idempotent algebra mitgeteilt werden $$ \ bar A \ EQUIV 1-A, \ QQUAD A \ Vee B \ EQUIV A + B -AB, \ QQUAD A \ Wedge B \ EQUIV A \ otimes B $$ < / span>

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 $$ \ phi= (A + B - AB) \ otimes (B-BC) \ otimes (A + C-2AC). $$

Dieser Ausdruck wird erweitert, um $ \ phi= ab - ABC $ zu geben. Ich möchte einen Algorithmus, der gegeben, da eine CNF-Formel als Input den Begriff mit der niedrigsten Homogenität ausgibt. In diesem Beispiel würde der Oracle $ AB $ zurückgeben. (Wenn es mehrere Bedingungen gibt, alle mit minimaler Homogenität, kann der Algorithmus jeden von ihnen zurückgeben.)

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 $ \ Epsilon $ haben, erhalten wir $$ \ phi= 4 \ Epsilon ^ 2 - 6 \ Epsilon ^ 3 + 2 \ Epsilon ^ 4. $$ Dies ergibt einen Homogenitätsvektor von $ [0,0,4, -6,2] $ .

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?

Answer 1

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 $ D $ aufweist, dann hat die Instanz eine erfüllende Zuordnung mit höchstens $ D $ solche.

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.