Decyzja, czy NC

Chciałbym zapytać o szczególny przypadek pytania „ Decyzja, czy dany obwód NC ⁰ oblicza permutację ” QiCheng, na który nie udzielono odpowiedzi.

Obwód boolowski nazywa się obwodem NC ⁰ _k , jeżeli każda bramka wyjściowa syntaktycznie zależy od co najwyżej k bramek wejściowych. (Mówimy, że bramka wyjściowa g syntaktycznie zależy od bramki wejściowej g ′, gdy w obwodzie jest skierowana ścieżka od g ′ do g, widziana jako ukierunkowany wykres acykliczny.)

We wspomnianym pytaniu QiCheng zapytał o złożoność następującego problemu, w którym k jest stałą:

Przykład : NC- ⁰ _k obwód z n -bitowe wejście i n wyjściu bitowych.
Pytanie : Czy dany obwód oblicza permutację na {0, 1} ⁿ ? Innymi słowy, czy funkcja obliczana przez obwód jest wstrząsiem z {0, 1} ⁿ do {0, 1} ⁿ ?

Jak Kaveh skomentował to pytanie, łatwo zauważyć, że problem dotyczy coNP. W odpowiedzi wykazałem, że problem jest kompletny coNP dla k = 5 i że występuje w P dla k = 2.

Pytanie . Jaka jest złożoność dla k = 3?

Wyjaśnienie z 29 maja 2013 r . : „Permutacja na {0, 1} ⁿ ” oznacza bijectywne mapowanie od {0, 1} ⁿ do siebie. Innymi słowy, problem dotyczy tego, czy każdy n- bitowy ciąg jest wyjściem danego obwodu dla jakiegoś n- bitowego ciągu wejściowego.

Ten problem z jest trudny coNP (a zatem coNP-zupełny).$k=3$

Aby to udowodnić, zredukuję z 3-SAT do uzupełnienia tego problemu (czy dla danego obwodu obwód ma funkcję nie-bijectywną).$NC_3^0$

Najpierw wstępna definicja, która będzie pomocna:

Definiujemy wykres oznaczony jako wykres ukierunkowany, którego niektóre krawędzie są oznaczone literałami, z tą właściwością, że każdy wierzchołek ma albo jedną nieznakowaną krawędź wejściową, jedną oznaczoną krawędź wejściową lub dwie nieznakowane krawędzie przychodzące.

Redukcja

Załóżmy, że mamy wzór 3-SAT składający się z m klauzul, z których każda zawiera trzy literały. Pierwszym krokiem jest zbudowanie oznaczonego wykresu G z ϕ . Ten wykres z etykietą zawiera jedną kopię następującego gadżetu (przepraszam za okropny schemat) dla każdej klauzuli w ϕ . Trzy krawędzie oznaczone L1, L2 i L3 są zamiast tego oznaczone literałami w klauzuli.$\phi$$m$$G$$\phi$$\phi$

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

Gadżety (po jednym dla każdej klauzuli) są ułożone w jednym dużym cyklu, a dół jednego gadżetu łączy się z górą następnego.

Zauważ, że taki układ gadżetów faktycznie tworzy wykres z etykietą (każdy wierzchołek ma stopień 1 lub 2 z tylko krawędziami prowadzącymi do etykietowania wierzchołków stopnia 1).

Na podstawie wzoru i oznaczonego wykresu G (który został skonstruowany z ϕ ) konstruujemy następnie obwód N C 0 3 (zakończy to redukcję). Liczba wejść i wyjść z tego układu jest brak + V , gdzie n oznacza liczbę zmiennych cp a v jest liczbą wierzchołków G . Jedno wejście i jedno wyjście jest przypisana do każdej zmiennej w cp i każdego wierzchołka w G . Jeśli x jest jakąś zmienną w $\phi$$G$$\phi$$NC_3^0$$n+v$$n$$\phi$$v$$G$$\phi$$G$$x$$\phi$wtedy będziemy odnosić się do bitów wejściowych i wyjściowych związanych z jako x i n i x o u t . Ponadto, jeśli l jest literałem przy l = x, wówczas definiujemy l i n = x i n, a jeśli l jest literałem przy l = ¬ x, to definiujemy l i n = ¬ x i n . Wreszcie, jeśli v jest jakimś wierzchołkiem w $x$$x_{in}$$x_{out}$$l$$l = x$$l_{in} = x_{in}$$l$$l = \neg x$$l_{in} = \neg x_{in}$$v$$G$następnie będzie odnosić się do bitów wejściowych i wyjściowych związane z jak V i n i V O U ţ .$v$$v_{in}$$v_{out}$

Istnieją cztery typy bitów wyjściowych:

1) Dla każdej zmiennej in ϕ , x o u t = x i n . Zauważ, że to wyjście zależy tylko od jednego bitu wejściowego.$x$$\phi$$x_{out} = x_{in}$

$v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$

$v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l_{in})$$l_{in}$$x_{in}$$x$$l$

$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

$NC_3^0$

$\phi$

$\phi$

$\phi$$G$

$\phi$$G$

$NC_3^0$

Rozważ cztery typy bitów wyjściowych:

$x$$\phi$$x_{out} = x_{in}$$x_{in}$

$v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$$G$$v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$$v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$

$v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l)$$l$$v_{in}$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$$l$$v_{in}$$(u, v)$$u$$u_{in} = 1$$u_{in} = v_{in}$$l$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$

$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$$u_{in} = L1$$w_{in}$$w_{in} = L2$$v_{in}$$v_{in} = L1 \lor L2$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$

$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$$u_{in} = L1 \lor L2$$w_{in}$$w_{in} = L3$$v_{in} = 1$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$$(L1 \lor L2 \lor L3) = 1$

$NC_3^0$

$\phi$

$\phi$$NC_3^0$

$x_{in}$$x$$\phi$$x$

$S$$v$$G$$v_{in}$

Poniżej udowodnimy następujące lematy:

$S$$S$

$S$$S$

$S$$G$$S$$S$

$(L1 \lor L2 \lor L3)$$(u, v)$$L$$v_{out} = v_{in} \oplus (u_{in} \land L)$$L = 0$$v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$$v_{in}$$v$$S$$S$

$S$$NC_3^0$

Pozostało tylko udowodnić lematy.

$G$$S$$S$$v_{out} = v_{in} \oplus X$$X$$v$$S$$X$$v_{in} = v_{out} \oplus X$$v$$S$

$S$$S$

Nie odpowiedź, której autor szukał, zobacz komentarze wyjaśniające, co to jest „permutacja” w tym kontekście.

Wykreśliłem rozmiar minimalnego dominującego zestawu dla digraphu włączenia grupy monogenicznej permutacji: https://oeis.org/A186202

Wszystko, co musisz zrobić, to przetestować jednego członka każdego rozkładu podstawowego.

Dla każdego pierwszego cyklu powinno wystarczyć zakodowanie elementów jako (10101010 ...), a następnie (01010101 ..)?

------ Wyjaśnienie ------ Celem tego podejścia jest modelowanie twoich przypadków testowych jako wykreślnika. Jeśli jeden udany przypadek testowy implikuje inny udany przypadek testowy, wystarczy przetestować tylko minimalny zestaw dominujący tego wykresu przestrzeni testowej. W obszarze permutacji OEIS A186202 to maksimum, które musisz przetestować, aby wykryć nietrywialną podgrupę lub udowodnić, że nie istnieje; ta liczba jest wciąż duża, ale znacznie mniejsza niż n !.

--Musing-- Używając n-1 zer i 1 jeden w iteracjach możesz wykryć stałą permutację, której szukasz. Następnie w O (n {(n-1) \ wybierz (k-1)} (2 ^ (k-1)) możesz przetestować, czy każdy zestaw zmiennych (k-1) nie wpływa na każdy indeks losowania Ponieważ skoro k jest ustalone, to jest wielomianowe. Czy czegoś brakuje?