Czy problem znalezienia operatorów spełniających listę zmiennych boolowskich NP jest kompletny?

Jest to podobne do SAT, z tym wyjątkiem, że znamy przypisanie każdej zmiennej, ale nie znamy przypisania żadnego operatora logicznego. Czy w takim przypadku znalezienie przypisania każdego operatora, aby wyrażenie oceniało na wartość logiczną, stanowi problem NPC?

Właściwie zastanawiałem się, czy znalezienie przypisania operatorów arytmetycznych w celu spełnienia liczby całkowitej arytmetycznej (np. = 10) jest NP zakończone?1 o p 1 3 o p 2 7 o p 3 o p $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$

Dodając i odejmując, myślę, że problem z partycją , który jest NP-trudny, redukuje się do drugiego problemu.

Biorąc pod uwagę zbiór S = { s 1 , s 2 , … , s n } tworzymy problem$S = \{s_1, s_2, \ldots, s_n\}$

s 1 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$

Jeśli istnieje rozwiązanie, tworzymy dwa zestawy:

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

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

Te dwa zestawy muszą mieć tę samą sumę w konfiguracji naszego pierwotnego problemu, więc problem partycji został rozwiązany. To pokazuje, że nie tylko trudno jest znaleźć rzeczywiste rozwiązanie tego problemu, ale w rzeczywistości trudno jest ustalić, czy istnieje rozwiązanie (przynajmniej w przypadku dodawania i odejmowania).

W przypadku zestawu operacji, który nie pozwala na tworzenie ujemnych liczb całkowitych, powiedzmy, mnożenie i dodawanie, nie jest to takie jasne. Pokazuje to również, że problem jest słabo NP-trudny; może wystąpić redukcja, która daje mocniejszy wynik niż ten.

Krótka odpowiedź. Wersja operatorska SAT jest sprawnie rozwiązywalna - przynajmniej, jeśli założymy dowolne obwody bram dwuwejściowych bez wentylacji, w stosunku do dowolnego pożądanego zestawu bramek.

Długa odpowiedź. Przyjmuję następującą postać problemu boolowskiego:

2-TREE-OPSAT. Biorąc pod uwagę wejście x ∈ { 0 , 1 } n dla n ⩾ 2 i zestaw bramek G składający się z 2-wejściowych bramek z jednym wyjściem, czy istnieje obwód C składający się z bramek w G, który przyjmuje x , to znaczy, który jest zadowolony, gdy podano dane wejściowe x (odwzorowanie bitów x na liście w obwodzie C w kolejności)?$x \in \{0,1\}^n$$n \geqslant 2$$\mathcal G$$C$$\mathcal G$ $x$$x$$x$$C$

W szczególności nie narzucamy żadnej szczególnej struktury na obwody C (oprócz binarnych drzew), nie pozwalamy na rozkładanie (aby każdy bit x był używany tylko raz), a bramki mogą być asymetryczne. Dopuszczając tylko bramki dwubitowe, wykluczam bramkę NOT (ale która może być symulowana poprzez posiadanie wielu bramek, które są ze sobą powiązane przez negacje, takie jak AND / NAND ; wykluczam również bramki, które po prostu generują stałe bez danych wejściowych , tak że liczba bramek w obwodzie będzie zawsze wynosić n - 1 dla wejścia n -bitowego . Ze względu na zwięzłość poniżej będę odnosił się do 2-TREE-OPSAT jako:$C$$x$$n-1$$n$OPSAT ; chociaż analiza problemu może stać się znacznie trudniejsza dla obwodów pozwalających na dowolne bramki wejściowe k ( K-TREE-OPSAT ) lub zezwalające na rozkręcenie (które możemy nazwać k-FANOUT-OPSAT ).

[ Zredagowano, aby dodać : możemy łatwo to dostosować, aby uwzględnić bardziej ogólny problem obecnej wersji twojego pytania, w którym próbujemy zmapować daną x ∈ { 0 , 1 } ∗ na wartość docelową b ∈ { 0 , 1 } , zamieniając role 0 i 1 w poniższej analizie; ma to wpływ na zamianę ról AND i OR , NAND i NOR , itd. ] $x \in \{0,1\}^\ast$$b \in \{0,1\}$$0$$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}}}$

W przypadku stałego wyboru problem wyboru odpowiedniego drzewa z odpowiednimi bramkami nie różni się niczym od logicznego rozłączenia: przy użyciu równoważników takich jak możemy dokonywać redukcji między kolekcjami, odnosząc bardziej skomplikowane zestawy bramek do prostych (i potężnych) zestawów bramek; a może mówić o tym, że jeden zestaw bramek może emulować inne bramy nienależące do zestawu, mądrze wybierając jakiś element który ma taki sam efekt (gdy jest przedstawiany z konkretnym wejściem) jak brama . W szczególności niektóre kombinacje bramek (takie jak ) mogą symulować stałą funkcję, dającx ∈ { 0 , 1 } n LUB ( x , y $x \in \{0,1\}^n$≡( ORAZ(x,y)∨PARITY ( x , y ) ) G G ∉ G { LUB , NAND }

Kontynuujemy rozważanie zestawów bram obejmujących różne typy bramek , później wykluczając te bramki z późniejszych przypadków analizy, aby wykazać, że zestawy bramek obejmujące dowolną z bram prowadzą do możliwego do rozwiązania problemu. Będziemy postępować w kolejności liczby ciągów 2-bitowych, które spełniają daną bramkę, zaczynając od stałej bramki do stałej bramki.G 1 $G$$1$$0$

1. Dla każdego zestawu bramek które zawierają stałą bramkę , możemy po prostu zbudować obwód przy użyciu samej bramki, w którym to przypadku akceptuje dowolne .$\mathcal G$ G ( x , y ) = 1 C C $G(x,y) = 1$$C$$C$$x$

2. LUB i NAND. Dla każdego zestawu bramek który zawiera : jeśli wszystkie inne bramki spełniają , to nie ma żadnej korzyści, aby wybrać inną bramę, ale w budynku obwód . Obwód tylko bramek przyjmuje dowolny ciąg oprócz . W przeciwnym razie istnieje bramka taka że jest tautologiczna. Tak więc każda instancja OPSAT z jest łatwa; i podobne uwagi odnoszą się do .G LUB G ∈ G G ( x , y $\mathcal G$$\OR$$G \in \mathcal G$⟹LUB ( x , y ) LUB C LUB x ∈ 0 ∗ G ∈ G { G , $G(x,y) \implies \OR(x,y)$$\OR$$C$$\OR$$x \in 0^\ast$$G \in \mathcal G$ } LUB ∈ G NAND ∈ $\{G, \OR\}$$\OR \in \mathcal G$$\NAND \in \mathcal G$

3. Bramy podobne do implikacji. Weźmy pod uwagę bramkę , która wyprowadza zero, tylko jeśli . W dalszej części podobna analiza będzie stosowana dla bramki . Rozważ dowolny ciąg . Jeśli kończy się na , na podciągi w postaci ; na każdym takim , rekurencyjnie stosujemy od prawej do lewej, co daje wynik dla każdego . (Dla podłańcucha o długości 1 używamy trywialnego obwodu, tzn. Pozostawmy to wejście w spokoju.) Podobnie, jeśliG ( x , y ) = ¬ x ∨ y ( x , y ) = ( 1 , 0 ) G ′ ( x , y ) = x ∨ ¬ y x ∈ { 0 , 1 } n x 0 x w j = 1 ∗ 0 w j j = 0 ∗ 1 G w $G(x,y) = \neg x \ou y$$(x,y) = (1,0)$$G'(x,y) = x \ou \neg y$
   
   $x \in \{0,1\}^n$$x$$0$$x$$w_j = 1^\ast 0$$w_j$ G 0 w j x 1 x $G$$0$$w_j$$x$ kończy się na , rozkłada na podciągi postaci i rekurencyjnie stosuje od lewej do prawej na każdym , co daje wynik dla każdego . W ten sposób możemy zredukować problem do budowy obwodów, które są spełnione albo o albo , gdzie jest liczbą podciągów lub . W przypadku możemy zaakceptować użycie bramek poprzez rekurencyjne stosowanie od lewej do prawej. To po prostu opuszcza sprawę$1$$x$$w_j =0^\ast 1$$G$$w_j$ 1 w j 0 m 1 $1$$w_j$$0^m$$1^m$ m 1 ∗ 0 0 ∗ 1 m ⩾ 2 G G m = 1 x ∈ 1 ∗ 0 x = 1 ∗ 0 G 1 ∗ 0 0 G H ∈ G H ( 1 , 0 ) = 1 { G , $m$$1^\ast0$$0^\ast 1$$m \geqslant 2$$G$$G$$m = 1$ , dla których problematycznym przypadkiem są dane wejściowe . Dla , każdy obwód składający się tylko z bramek da tylko krótsze łańcuchy w postaci , ostatecznie dając łańcuch jednobitowy : tak, że żaden obwód bramek może być spełniony przez to wejście. Jeśli istnieje również bramka dla której , to jest tautologiczna; lub, jeśli istnieje bramka dla której , możemy zmniejszyć ciągi znaków o postaci$x \in 1^\ast 0$
   
   $x= 1^\ast 0$$G$$1^\ast 0$$0$$G$$H \in \mathcal G$$H(1,0) = 1$} H ∈ G H ( 1 , 1 ) = 0 11 ∗ 0 ( 1 ∗ 0 ) ∗ H x x ∈ 1 ∗$\{G,H\}$$H \in \mathcal G$$H(1,1) = 0$$11^\ast 0$do ciągów formy , przez zastosowanie do pierwszych dwóch bitów . W przeciwnym razie nie można zbudować obwodu, który akceptuje . Zatem dla każdego zestawu bramek G, który zawiera bramę implikacyjną, OPSAT jest łatwy.$(1^\ast 0)^\ast$$H$$x$$x \in 1^\ast 0$
   
   $\mathcal G$

4. Negacje prognoz. Rozważmy bramki ¬ π 1 ( x , y ) = ¬ x i . Uważamy , analiza z jest podobna. Własnych, może przyjąć dowolny łańcuch znaków dla przez redukcję końcowego bity do jednego kawałka, a następnie zastosowanie ; i podobnie może przyjąć dla poprzez zmniejszenie końcowego$\neg \pi_1(x,y) = \neg x$¬ π 2 ( x , y ) = ¬ y ¬ π 1 ¬ π 2 ¬ π 1 0 ( 0 | 1 ) n - 1 n ⩾ 2 n - 1 ¬ π 1 1 ( 0 | 1 ) n - $\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 ⩾ 3 n - 2 ¬ π 1 ( ¬ π 1$n \geqslant 3$$n-2$bitów na pojedynczy bit, a następnie zastosowanie obwodu . Jedynymi wejściami, których obwody nie mogą zaakceptować, są wtedy lub ; ustalenie, czy jakakolwiek dodatkowa bramka je akceptuje, jest banalne. Tak więc OPSAT jest łatwy do negacji projekcji.x 1 , x 2 ) , x 3 ) ¬ π 1 10 $\neg \pi_1(\neg \pi_1(x_1, x_2),x_3)$$\neg \pi_1$$10$$11$

5. RÓWNOŚĆ I RÓWNOŚĆ . Rozważ bramę . Zestaw bramek oczywiście może być spełniony tylko przez ciągi o nieparzystej liczbie 1s; rozważamy korzyści wynikające z dodania dowolnej innej bramy.PARITY ( x , y ) = ( x ∨ ¬ y ) ∧ ( ¬ x ∨ y ) G = { PARITY } x ∈ { 0 , 1 } $\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$$\mathcal G = \{\PARITY\}$$x \in \{0,1\}^n$

   • Każdy zestaw bramek, który zawiera zarówno i lub może symulować obwody zawierające odpowiednio lub dla stałych wejść, które są łatwe przypadki OPSAT .RODZAJ I NOR ( x , y ) = ¬ ( x ∨ y ) LUB $\PARITY$$\AND$$\NOR(x,y) = \neg(x \ou y)$$\OR$$\NAND$
   • Można lub do symulacji lub na dwubitowych podciągach o parzystej parzystości, abyśmy mogli zmniejszyć te zestawy bram bramy i do poprzedniego przypadku.π 1 ( x , y ) = x π 2 ( x , y ) = y AND NOR $\pi_1(x,y) = x$$\pi_2(x,y) = y$$\AND$$\NOR$$\PARITY$
   • PARITY EQUAL = ¬ $\PARITY$ wraz z jest tautologią.$\EQUAL = \neg \PARITY$
   • Jeśli uzupełnimy bramką , możemy zaakceptować dowolny ciąg parzystości z wyjątkiem , stosując do -substring z i stosując obwód do reszty. Podobnie wraz z może zaakceptować dowolny ciąg oprócz tych o postaci . Uzupełnienie zarówno i pozwala nam budować obwody, które akceptują wszystkie wejścia oprócz iPARITY G 01 = ¬ x ∧ y x ∈ ( $\PARITY$$G_{01} = \neg x \et y$ ) ∗ 0 ∗ G 01 01 x PARITY PARITY G 10 = x ∧ ¬ y x ∈ 0 ∗ ( 11 ) ∗ PARITY G $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 ∈ 0 ∗ x = $G_{10}$$x \in 0^\ast$$x = 11$ .
   • Wreszcie, jeśli uzupełnimy stałą bramką , możemy zaakceptować dowolne dane wejściowe z wyjątkiem lub przez zastosowanie bramki do podłańcuch lub , redukujący do nieparzystej wielkości parzystości.PARITY Z ( x , y ) = 0 x ∈ ( 11 ) $\PARITY$$Z(x,y) = 0$$x \in (11)^\ast$ x ∈ 0 ∗ G 01 $x \in 0^\ast$$G$$01$$10$

   Tak więc OPSAT jest łatwy dla każdego matematycznego zawierającego . Podobna analiza ma zastosowanie do bramki jak do bramki : ponieważ , obwody o bramy w zasadzie liczyć parzystości liczby S na wejściu. Możemy wtedy zredukować analizę dla do analizy , wymieniając i .G PARITY EQUAL PARITY EQUAL ( x , y ) = ¬ PARITY ( x , y ) = ¬ PARITY ( ¬ x , ¬ y ) EQUAL$\mathcal G$$\PARITY$
   
   $\EQUAL$$\PARITY$$\EQUAL(x,y) = \neg \PARITY(x,y) = \neg \PARITY(\neg x, \neg y)$$\EQUAL$$0$ EQUAL PARITY 0 $\EQUAL$$\PARITY$$0$$1$

6. Bramki projekcyjne. Bramy i , wzięte samodzielnie, mogą budować tylko obwody, które akceptują odpowiednio łańcuchy rozpoczynające się lub kończące na . Rozważ efekt powiększenia bramki dowolną inną bramą (podobna analiza dotyczy ):π 1 ( x , y ) = x π 2 ( x , y $\pi_1(x,y) = x$ = y 1 π 1 π $\pi_2(x,y) = y$$1$$\pi_1$$\pi_2$

   • Zezwolenie na i pozwala na zbudowanie obwodu „selekcyjnego”, który po prostu wysyła dowolny bit z wejścia; mogą one przyjmować dowolne , a uzupełnienie ich dowolną bramką dla której umożliwia zbudowanie satysfakcjonującego obwodu dla dowolnego .π 1 π 2 x ≠ 0 $\pi_1$$\pi_2$$x \ne 0^n$ G G ( 0 , 0 ) = 1 $G$$G(0,0) = 1$$x$
   • Jeśli uzupełnimy albo albo , możemy symulować albo albo implikacyjną bramę dla stałych danych wejściowych; OPSAT został rozwiązany dla obu tych przypadków.π 1 $\pi_1$$\NOR$ G 01 = ¬ x ∧ y $G_{01} = \neg x \et y$$\OR$
   • Jeśli uzupełnimy albo , , stałą bramką lub dowolną ich kombinacją, nie otrzymamy żadnej dodatkowej mocy akceptującej, więc nadal akceptuje tylko ciągi rozpoczynające się od .π 1 AND G 10 = x ∧ $\pi_1$$\AND$ y Z ( x , y ) = 0 $G_{10} = x \et \neg y$$Z(x,y) = 0$$1$

   Tak więc dla każdej innej bramki, którą możemy uzupełnić (lub ), uzyskujemy albo zestaw tautologiczny, nie uzyskujemy żadnej dodatkowej mocy akceptującej tylko na (lub ), lub możemy zredukować do wcześniejszego łatwego przypadku OPSAT . Wówczas dowolne wystąpienie OPSAT z lub jest łatwe.π 1 π 2 π 1 π $\pi_1$$\pi_2$$\pi_1$$\pi_2$ π 1 ∈ G π 2 ∈ $\pi_1 \in \mathcal G$$\pi_2 \in \mathcal G$

7. Bramy z funkcją delta. Rozważmy dwubitowe bramki, dla których istnieje tylko jedno wejście, które je spełnia: , , , i . Obwody wykonane tylko za pomocą bramek mogą zaakceptować tylko ciąg : uzupełnienie ich dowolną inną bramką z funkcją delta pozwala im symulować albo , , albo , które są rozwiązanymi przypadkami; podobne uwagi dotyczą . Zestawu bramek można również użyć do symulacjiORAZ NOR G 10 ( x , y ) = x ∧ ¬ y G 01 ( x , y ) = ¬ x ∧ y ORAZ 1 ∗ RÓWNY π 1 π 2 NOR { G 01 , G 10 } PARITY G 10 G 01 Z ( $\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$brama. Możemy zatem skupić się na bramce lub , ewentualnie uzupełnionej bramką . Koncentrujemy się na , przy czym przypadek jest podobny. Obwody wykonane z samego można zbudować tak, aby akceptowały , z wyjątkiem ciągu , poprzez zastosowanie dowolnego obwodu do końcowych bitów, a następnie zastosowanie obwodu . Oczywiście łańcuch nie może zostać zaakceptowany przez lub ; i możemy indukcyjnie pokazać, że każdy$G_{10}$$G_{01}$ , y ) = 0 G 10 G $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 ∈ 1 ( 0 | 10 | 11 ) ( 0 | 1 ) $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}$obwód przyjmujący ciąg musi mieć pośrednie wyniki bramek w skrajnej lewej gałęzi, z których wszystkie dają , aż do samego lewego skrajnego wejścia. Dodanie bramek nie daje żadnych dodatkowych korzyści . Dlatego obwody akceptują tylko .$1$$Z$$G_{10}$$x \in 1(0|10|11)(0|1)^\ast$

8. Wreszcie obwody złożone tylko z bramek nie przyjmują żadnych sygnałów wejściowych.$Z$

Ponieważ każda brama prowadzi do dobrze zdefiniowanego i na ogół dość dużej klasy wejść, które przyjmuje z dodatkowymi bram tendencję do bagatelizowania problemu, okazuje się, że 2-TREE-OPSAT jest w P .