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.

— Tsuyoshi Ito
źródło

Notatka osobista: kiedy opublikowałem odpowiedź na pytanie QiCheng, zrobiłem to tylko dlatego, że problem wyglądał interesująco, bez żadnej konkretnej aplikacji. Kilka miesięcy później znalazłem się w sytuacji, w której musiałem wytłumaczyć komuś, że podjęcie decyzji, czy dany program oblicza permutację, nie jest wcale trywialne. Dzięki pytaniu QiCheng miałem doskonały przykład (co za zbieg okoliczności!). Potem bardziej zainteresowałem się przypadkami k = 3 i k = 4. Podejrzewam, że przypadek k = 3 jest już zakończony coNP, ale nie byłem w stanie udowodnić żadnej z tych metod.

— Tsuyoshi Ito

ten problem wydaje się być szczególnym przypadkiem problemu Pigeonhole Circuit zdefiniowanego przez Papadimitriou ( sciencedirect.com/science/article/pii/S0022000005800637 ), który jest kompletny dla PPP w odniesieniu do redukcji czasu między problemami wyszukiwania.

— Marcos Villagra,

@Marcos Villagra: Dziękuję za komentarz, ale obawiam się, że mówiąc „szczególny przypadek” znacząco zmieniasz definicję problemu obwodu gołębia. Ważną właściwością problemu Pigeonhole Circuit jest to, że jest to całkowity problem z wyszukiwaniem, podczas gdy aktualny problem (postrzegany jako problem z wyszukiwaniem dwóch danych wejściowych, które dają takie same dane wyjściowe) nie jest całkowitym problemem z wyszukiwaniem.

— Tsuyoshi Ito

Odpowiedzi:

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 klauzul, z których każda zawiera trzy literały. Pierwszym krokiem jest zbudowanie oznaczonego wykresu 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 (który został skonstruowany z ) konstruujemy następnie obwód (zakończy to redukcję). Liczba wejść i wyjść z tego układu jest , gdzie oznacza liczbę zmiennych a jest liczbą wierzchołków . Jedno wejście i jedno wyjście jest przypisana do każdej zmiennej w i każdego wierzchołka w . Jeśli 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 i . Ponadto, jeśli jest literałem przy wówczas definiujemy a jeśli jest literałem przy to definiujemy . Wreszcie, jeśli 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 i . $v$ $v_{in}$ $v_{out}$

Istnieją cztery typy bitów wyjściowych:

1) Dla każdej zmiennej in , . 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$ $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$ $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$

— Michaił Rudoy
źródło

-1

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?

— Chad Brewbaker
źródło

Hmm Nie jestem pewien, czy (01) *, (10) * jest wystarczające. Może być konieczne wypróbowanie wszystkich konfiguracji 2 ^ p dla każdego cyklu głównego.

— Chad Brewbaker

(2^{n})!

$(2^n)!$

n - 1

$n-1$

1

$1$

C : {0, 1}^{n} \to {0, 1}^{n}

$C:\{0,1\}^n \to \{0,1\}^n$

x, x^{'} \in {0, 1}^{n}

$x,x' \in \{0,1\}^n$

C (x) = C (x^{'})

$C(x)=C(x')$

x \neq x^{'}

$x \ne x'$

C

$C$ permutuje (tasuje / reorganizuje / ponownie porządkuje) bity wejściowe. Czy widzisz różnicę? Podejrzewam, że odpowiedziałeś na niewłaściwe pytanie.

— DW

Dziękuję za próbę pomocy, ale jak wyjaśnił DW, obawiam się, że pytanie, na które odpowiedziałeś, jest inne niż zadane. „Permutacja na {0,1} ^ n” oznacza funkcję podwójną od {0,1} ^ n do siebie i nie oznacza przestawienia n bitów.

— Tsuyoshi Ito

Chad, czy mógłbyś usunąć tę odpowiedź lub przynajmniej dodać notatkę na górze, że to nie odpowiada na pytanie Tsuyoshi?

— Kaveh

Decyzja, czy NC

Redukcja

ϕϕ\phi

ϕϕ\phi

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

$\phi$

$\phi$