Ist das Problem, Operatoren zu finden, die eine Liste der booleschen Variablen NP erfüllen, vollständig?

Dies ist ähnlich wie bei SAT, außer dass wir die Zuordnung jeder Variablen kennen, aber die Zuweisung eines booleschen Operators nicht kennen. Ist es in diesem Fall ein NPC-Problem, die Zuordnung jedes Operators so zu finden, dass der Ausdruck einen bestimmten booleschen Wert ergibt?

Eigentlich habe ich mich gefragt, ob die Zuordnung von arithmetischen Operatoren zur Erfüllung eines ganzzahligen arithmetischen Ausdrucks (z. B. o p 1 3 o p 2 7 o p 3 o p 4 = 10) NP vollständig ist.$1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$

Mit Addition und Subtraktion reduziert sich das Partitionsproblem , das NP-schwer ist, auf Ihr zweites Problem.

Bei einer Menge erzeugen wir das Problem$S = \{s_1, s_2, \ldots, s_n\}$

o p 1 s 2 o p 2 s 3 o p 3 … o p n - 1 s n = 0 . $s_1$ $op_1$ $s_2$ $op_2$ $s_3$ $op_3$ $\ldots op_{n-1}$ $s_n = 0$

Wenn eine Lösung existiert, erstellen wir zwei Mengen:

$S_1 = \{s_1\}\cup \{s_i | op_{i-1} = +\}$

$S_2 = \{s_i | op_{i-1} = -\}$

Diese beiden Sätze müssen bei der Einrichtung unseres ursprünglichen Problems dieselbe Summe haben, damit das Partitionsproblem gelöst ist. Dies zeigt, dass es nicht nur schwierig ist, die eigentliche Lösung für dieses Problem zu finden, sondern dass NP tatsächlich schwer zu bestimmen ist, ob eine Lösung existiert (zumindest für Addition und Subtraktion).

Für eine Reihe von Operationen, bei denen keine negativen Ganzzahlen erstellt werden können, z. B. Multiplikation und Addition, ist dies nicht so klar. Dies zeigt auch nur, dass das Problem schwach NP-hart ist; Möglicherweise gibt es eine Reduzierung, die zu einem stärkeren Ergebnis führt.

Kurze Antwort. Die Operator-Version von SAT ist effizient lösbar - zumindest, wenn wir beliebige Schaltungen von Gates mit zwei Eingängen ohne Fan-Out über eine beliebige Wahl des Gate-Sets annehmen.

Lange Antwort. Ich nehme die folgende Form des Booleschen Problems an:

2-BAUM-OPSAT. Gibt es bei einem Eingang für n ⩾ 2 und einem Gatesatz G, der aus Gattern mit zwei Eingängen und einem Ausgang besteht, eine Schaltung C, die aus Gattern in G besteht, die akzeptiert$x \in \{0,1\}^n$$n \geqslant 2$$\mathcal G$$C$$\mathcal G$ , d.erfüllt, wenn der Eingang x gegeben ist (Abbildung der Bits von x auf die Blätter der Schaltung C in der Reihenfolge)?$x$$x$$x$$C$

Insbesondere legen wir den Schaltungen keine bestimmte Struktur auf (abgesehen davon, dass es sich um Binärbäume handelt), lassen kein Fan-Out zu (so dass jedes Bit von $C$$x$ nur einmal verwendet wird), und die Gates können asymmetrisch sein. Indem ich nur Zwei-Bit-Gatter zulasse, schließe ich das NICHT- Gatter aus (das jedoch simuliert werden kann, indem mehrere Gatter vorhanden sind, die durch Negationen wie AND / NAND miteinander verbunden sind , und ich schließe auch Gatter aus, die einfach Konstanten ohne Eingaben ausgeben , so dass die Anzahl der Gatter in der Schaltung für einen n- Bit-Eingang tatsächlich immer . Der Kürze halber bezeichne ich 2-TREE-OPSAT im Folgenden einfach als$n-1$$n$OPSAT ; Die Analyse des Problems kann jedoch für Schaltungen, die beliebige k- Eingangsgatter ( k-TREE-OPSAT ) oder Fan-out (was wir als k-FANOUT-OPSAT bezeichnen könnten ) zulassen, viel schwieriger werden .

[ Bearbeitet, um hinzuzufügen : Wir können dies leicht anpassen, um das allgemeinere Problem der aktuellen Überarbeitung Ihrer Frage zu berücksichtigen, bei der wir versuchen, ein gegebenes einem Zielwert b ∈ { 0 , 1 zuzuordnen } durch Vertauschen der Rollen von 0 und$x \in \{0,1\}^\ast$$b \in \{0,1\}$$0$ in der folgenden Analyse; Dies hat den Effektdie Rollen von VertauschenANDundOR,NANDundNOR,usw.] $1$$\def\et{\wedge}\def\ou{\vee}\def\AND{\mathop{\text{AND}}}\def\NAND{\mathop{\text{NAND}}}\def\OR{\mathop{\text{OR}}}\def\NOR{\mathop{\text{NOR}}}\def\EQUAL{\mathop{\text{EQUAL}}}\def\PARITY{\mathop{\text{PARITY}}}$

Für eine feste Wahl von ist das Problem der Auswahl eines geeigneten Baums mit geeigneten Toren einer logischen Disjunktion nicht unähnlich: Verwendung von Äquivalenzen wie OR ( x , y $x \in \{0,1\}^n$ Wir können Reduzierungen zwischen Sammlungen durchführen, die kompliziertere Gate-Sets mit einfachen (und leistungsstarken) Gate-Sets in Verbindung bringen. a kann aus einem Gatesatz sprichtLage, andere Tore nicht zu dem Satz gehörenzu emulieren, indem wiese ein Element der Wahl G , die die gleiche Wirkung hat wie ein Tor (wennmit einem bestimmten Eingang vorgelegt) G ∉ G . Insbesondere bestimmte Kombinationen von Toren (wie { OR

Wir gehen vor, indem wir Gatesätze betrachten, die verschiedene Arten von Gates , und diese Gates später aus späteren Fällen der Analyse ausschließen, um zu zeigen, dass Gatesets, an denen eines der Gates beteiligt ist, zu einem handhabbaren Problem führen. Wir werden in der Reihenfolge der Anzahl der Zwei-Bit-Strings fortfahren, die das fragliche Gate erfüllen, beginnend mit dem Gate mit konstanter 1 bis zum Gate mit konstanter 0 .$G$$1$$0$

1. Für jede Gate-Menge die das konstante Gate G ( x , y ) = 1 enthält , können wir einfach eine Schaltung C nur unter Verwendung dieses Gates bauen. In diesem Fall akzeptiert C jedes x .$\mathcal G$$G(x,y) = 1$$C$$C$$x$

2. ODER und NAND. Für jede Gate-Menge die OR enthält : Wenn alle anderen Gates G ∈ G G ( x , y ) erfüllen$\mathcal G$$\OR$$G \in \mathcal G$ , dann ist es kein Vorteil, ein anderes Gatter als ODER beim Aufbau der Schaltung C zu wählen. Eine Schaltung mit nur ODER- Gattern akzeptiert eine beliebige Zeichenfolge außer x ∈ 0 ∗ . Ansonsten existiert ein Gate G ∈ G, so dass { G , OR } tautolog ist. Jede Instanz vonOPSATmit OR ∈ G ist also einfach; und ähnliche Bemerkungen gelten für$G(x,y) \implies \OR(x,y)$$\OR$$C$$\OR$$x \in 0^\ast$$G \in \mathcal G$$\{G, \OR\}$$\OR \in \mathcal G$ .$\NAND \in \mathcal G$

3. Implikationsähnliche Tore. Betrachten Sie das Gate , das nur dann Null ausgibt, wenn ( x , y ) = ( 1 , 0 ) . Für das Folgende gilt eine ähnliche Analyse für das Gate G ' ( x , y ) = x ∨ ¬ y . Betrachten Sie eine beliebige Zeichenfolge x ∈ { 0 , endet mit 0 , zerlegen Sie $G(x,y) = \neg x \ou y$$(x,y) = (1,0)$$G'(x,y) = x \ou \neg y$
   
   . Wenn$x \in \{0,1\}^n$$x$$0$$x$ in Teilzeichenfolgen der Form ; auf jedes solche w j wenden wir rekursiv G von rechts nach links an, was die Ausgabe 0 für jedes w j ergibt . (Für einen Teilstring der Länge 1 verwenden wir die Trivialschaltung, dh lassen Sie diesen Eingang in Ruhe.) Wenn x mit 1 endet , zerlegen Sie x in Teilstrings der Form w j = 0 ∗ 1 und wenden Sie G rekursiv von links nach an direkt auf jedem$w_j = 1^\ast 0$$w_j$$G$$0$$w_j$$x$$1$$x$$w_j =0^\ast 1$$G$ , was die Ausgabe 1 für jedes w j ergibt = 1 , für den der problematische Fall Eingaben x ∈ $w_j$$1$$w_j$. So können wir das Problem für den Aufbau Schaltungen verringern , die entweder durch zufrieden ist oder 1 m , wobei m die Anzahl des Teils ist 1 * 0 oder 0 * 1 . Für m ⩾ 2 , können wir entweder unter Verwendung akzeptieren G durch rekursiv Anwendung Gates G von links nach rechts. Dies lässt nur den Fall $0^m$$1^m$$m$$1^\ast0$$0^\ast 1$$m \geqslant 2$$G$$G$$m = 1$ . Für x = 1 ∗ 0 ergibtjede Schaltung, die nur aus G- Gattern besteht, nur kürzere Zeichenfolgen der Form 1 ∗ 0 , was letztendlich die Einzelbit-Zeichenfolge 0 ergibt: so dass keine Schaltung von G- Gattern durch diese Eingabe erfüllt werden kann. Wenn esauchein Gate H ∈ G gibt, für das H ( 1 , 0 ) = 1 ist , dann ist { G , H } tautolog; oder wenn es ein Tor$x \in 1^\ast 0$
   
   $x= 1^\ast 0$$G$$1^\ast 0$$0$$G$$H \in \mathcal G$$H(1,0) = 1$$\{G,H\}$ für das H ( 1 , 1 ) = 0 ist , können wir Zeichenfolgen der Form 11 ∗ 0 auf Zeichenfolgen der Form ( 1 ∗ 0 ) ∗ reduzieren Somit istOPSATfür jeden Gate-Satz G, der einimplikationsähnlichesGate enthält,einfach.$H \in \mathcal G$$H(1,1) = 0$$11^\ast 0$$(1^\ast 0)^\ast$durch Anwenden von auf die ersten beiden Bits von x . Andernfalls kann keine Schaltung aufgebaut werden, die x ∈ 1 ∗ 0 akzeptiert .$H$$x$$x \in 1^\ast 0$
   
   $\mathcal G$

4. $\neg \pi_1(x,y) = \neg x$$\neg \pi_2(x,y) = \neg y$$\neg \pi_1$$\neg \pi_2$$\neg \pi_1$$0(0|1)^{n-1}$$n \geqslant 2$$n-1$$\neg \pi_1$$1(0|1)^{n-1}$$n \geqslant 3$$n-2$$\neg \pi_1(\neg \pi_1(x_1, x_2),x_3)$$\neg \pi_1$$10$$11$

5. $\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$$\mathcal G = \{\PARITY\}$$x \in \{0,1\}^n$

   • $\PARITY$$\AND$$\NOR(x,y) = \neg(x \ou y)$$\OR$$\NAND$
   • $\pi_1(x,y) = x$$\pi_2(x,y) = y$$\AND$$\NOR$$\PARITY$
   • $\PARITY$$\EQUAL = \neg \PARITY$
   • $\PARITY$$G_{01} = \neg x \et y$$x \in (11)^\ast 0^\ast$$G_{01}$$01$$x$$\PARITY$$\PARITY$$G_{10} = x \et \neg y$$x \in 0^\ast (11)^\ast$$\PARITY$$G_{01}$$G_{10}$$x \in 0^\ast$$x = 11$
   • $\PARITY$$Z(x,y) = 0$$x \in (11)^\ast$$x \in 0^\ast$$G$$01$$10$

   $\mathcal G$$\PARITY$
   
   $\EQUAL$$\PARITY$$\EQUAL(x,y) = \neg \PARITY(x,y) = \neg \PARITY(\neg x, \neg y)$$\EQUAL$$0$ s in der Eingabe. Wir können dann die Analyse für reduzieren$\EQUAL$$\PARITY$$0$$1$

6. $\pi_1(x,y) = x$$\pi_2(x,y) = y$$1$$\pi_1$$\pi_2$

   • $\pi_1$$\pi_2$$x \ne 0^n$$G$$G(0,0) = 1$$x$
   • $\pi_1$$\NOR$$G_{01} = \neg x \et y$$\OR$
   • $\pi_1$$\AND$$G_{10} = x \et \neg y$$Z(x,y) = 0$$1$

   $\pi_1$$\pi_2$$\pi_1$$\pi_2$$\pi_1 \in \mathcal G$$\pi_2 \in \mathcal G$

7. $\AND$$\NOR$$G_{10}(x,y) = x \et \neg y$$G_{01}(x,y) = \neg x \et y$$\AND$$1^\ast$$\EQUAL$$\pi_1$$\pi_2$$\NOR$$\{G_{01}, G_{10}\}$$\PARITY$$G_{10}$$G_{01}$$Z(x,y) = 0$$G_{10}$$G_{01}$
   
   $G_{10}$$1(0|1)^{n-1}$$11$$n-2$$G_{10}(x_1, G_{10}(x_2, x_3))$$11$$G_{10}$$Z$$G_{10}$$1$$Z$$G_{10}$$x \in 1(0|10|11)(0|1)^\ast$

8. $Z$

Da jedes Gate zu einer genau definierten und im Allgemeinen recht großen Klasse von Eingaben führt, die es akzeptiert, wobei zusätzliche Gates dazu neigen, das Problem zu trivialisieren, finden wir, dass 2-TREE-OPSAT in P ist .