Decydowanie, czy dany obwód

Jaka jest złożoność decyzji, czy obwód z bitami wejściowymi i bitami wyjściowymi oblicza permutację ? innymi słowy, czy każdy ciąg bitów w jest wyjściem obwodu dla niektórych danych wejściowych? Wygląda na problem, który został zbadany, ale nie mogę znaleźć żadnych odniesień. $\mathsf{NC}^0$ $n$ $n$ $\{0,1\}^n$ $\{0,1\}^n$

cc.complexity-theory circuit-complexity permutations

— QiCheng
źródło

Oczywistym jest związana

, który działa również

(sprawdzenie, czy funkcja jest za pomocą wstrzyknięć).

c o N P

$\mathsf{coNP}$

P

$\mathsf{P}$

— Kaveh,

Co rozumiesz przez „obwód NC0”? Zwyczajową frazą jest „rodzina obwodów NC0”, która (być może niestety) jest często skracana do „obwodu NC0”, ale nie sądzę, że masz na myśli rodzinę obwodów NC0 w swoim pytaniu.

— Tsuyoshi Ito,

Przez obwód

rozumiem, że każdy bit wyjściowy obwodu zależy tylko od stałej liczby bitów wejściowych.

N C^{0}

$NC^0$

— QiCheng,

Tak, pytam o rodzinę. Aby to wyjaśnić, możesz zmienić

gdzie każdy bit wyjściowy zależy tylko od

bitów wejściowych w rodzinie.

N C^{0}

$NC^0$

N C_{5}^{0}

$NC_5^0$

5

$5$

— QiCheng

To nie odpowiada na twoje pytanie, ale jeśli problem jest uogólniony, tak że każdy bit wyjściowy może zależeć od bitów wejściowych O (log n), myślę, że problem jest coNP kompletny w ramach zdolności Turinga. Wynika to z kompletności coNP skończonej odwracalności dwuwymiarowych automatów komórkowych ( Durand 1994 ) poprzez reprezentowanie każdej komórki w dwuwymiarowych automatach komórkowych jako ciąg binarny O (log n).

— Tsuyoshi Ito

Twardość

Po twoim komentarzu do pytania nazwiemy obwód, w którym każdy bit wyjściowy zależy od co najwyżej k bitów wejściowych, „ obwodem NC ⁰_k ”. Używając tego terminu, twój problem jest kompletny coNP w przypadku obwodów NC ⁰₅ . Oznacza to, że następujący problem jest coNP-complete.

Instancja : A Boolean obwód C z n bitami wejściowymi i n bitami wyjściowymi, przy czym każdy bit wyjściowy zależy od maksymalnie pięciu bitów wejściowych.
Pytanie : Czy mapowanie od {0,1} ⁿ do siebie jest obliczane przez bijective C ?

Jak zauważył Kaveh, jest wyraźnie w CoNP, nawet bez ograniczenia liczby bitów wejściowych, od których zależy każdy bit wyjściowy. Aby udowodnić twardość coNP, zredukujemy 3SAT do uzupełnienia obecnego problemu. Kluczowa idea redukcji jest taka sama jak ta zastosowana w pracy [Dur94] autorstwa Duranda, o której wspomniałem w komentarzu do pytania, ale cała redukcja jest w naszym przypadku znacznie prostsza.

Biorąc pod uwagę wzór 3CNF φ z n zmiennymi i klauzulami m , konstruujemy obwód logiczny C z ( n + m ) bitami wejściowymi i ( n + m ) bitami wyjściowymi w następujący sposób. Bity wejściowe oznaczamy jako x ₁ ,…, x _n , y ₁ ,…, y _m , a bity wyjściowe jako x ′ ₁ ,…, x ′ _n , z ₁ ,…, z _m . Uważamy, że bity wejściowe x₁ ,…, x _n określ przypisanie prawdy do n zmiennych w φ .

x ′ _i = x _i dla 1 ≤ i ≤ n . Oznacza to, że pierwsze n bitów danych wejściowych jest zawsze kopiowane do pierwszych n bitów danych wyjściowych.
Dla 1 ≤ i ≤ m , jeśli i- ta klauzula φ jest spełniona, to z _i = y _i ⊕ y _{i +1} , gdzie indeks dolny jest interpretowany modulo m . W przeciwnym razie z _i = y _i .

Zauważ, że każdy bit wyjściowy zależy od maksymalnie pięciu bitów wejściowych. Pomijam dowód poprawności redukcji, ale kluczową ideą (którą pożyczyłem od [Dur94]) jest to, że jeśli φ jest zadowalające, a bity wejściowe x ₁ ,…, x _n są ustawione na zadowalające przypisanie φ , to m bitów wyjściowych z ₁ , ..., z _m są ograniczone mieć kontroli parzystości i dlatego układ nie może być permutacją. Z drugiej strony, jeśli bity wejściowe x ₁ ,…, x _n są ustawione na niespełniające przypisanie φ , to bity wyjściowe z₁ ,…, z _m można ustawić na dowolną wartość; z tego powodu, jeśli φ jest niezadowalające, to obwód jest permutacją.

Ustępliwość

Po stronie możliwej do rozwiązania problem występuje w P w przypadku obwodów NC ⁰₂ . Jest to pokazane w następujący sposób. Zasadniczo każdy bit wyjściowy w obwodzie boolowskim dla permutacji jest zrównoważony ; tj. dokładnie połowa ciągów wejściowych ustawia bit wyjściowy na 1. Jednak każda zbalansowana funkcja boolowska od {0,1} ² do {0,1} jest afiniczna ; tj. kopia pojedynczego bitu wejściowego, XOR dwóch bitów wejściowych lub ich negacja. Dlatego możemy najpierw sprawdzić, czy każdy bit wyjściowy jest zbalansowany, a następnie sprawdzić bolesność przez eliminację Gaussa.

Nie znam złożoności w przypadku obwodów NC ⁰₃ lub w przypadku obwodów NC ⁰₄ .

Referencje

[Dur94] Bruno Durand. Inwersja automatów komórkowych 2D: niektóre wyniki złożoności. Theoretical Computer Science , 134 (2): 387–401, listopad 1994. DOI: 10.1016 / 0304-3975 (94) 90244-5 .

— Tsuyoshi Ito
źródło

I napisali kolejne pytanie o przypadku NC ^ 0_3 obwodów.

— Tsuyoshi Ito