Najmniejszy obwód boolowski do generowania języka

Rozważ niepusty język ciągów binarnych o długości . Mogę opisać za pomocą obwodu logicznego z wejściami i jednym wyjściem takim, że jest prawdą, iff : jest to dobrze znane.n L C n C ( w ) w ∈ $L$$n$$L$$C$$n$$C(w)$$w \in L$

Jednakże, chce reprezentować z logicznego obwodu z wyjść i pewną liczbę wejść, powiedzmy , tak, że zbiór wartości wyjściowych dla każdego z możliwe wejścia jest dokładnie .C ′$L$$C'$$n$ C ′ 2 m$m$$C'$$2^m$$L$

Biorąc pod uwagę , jak mogę znaleźć taki obwód o minimalnej wielkości i jaka jest złożoność? Czy istnieje związek między znanymi granicami dotyczącymi wielkości obwodów pierwszego rodzaju ( ) i obwodów drugiego rodzaju ( ), lub złożoność ich znalezienia?C ′ C C $L$$C'$$C$$C'$

(Zauważmy, że istnieje jakiś rodzaj dualizmu w następującym sensie: podany , mogę łatwo zdecydować, czy słowo wejścia jest w oceniając obwód, ale jest NP-trudne w ogóle znaleźć jakieś słowo znajdując przypisanie takie, że dane wyjściowe są prawdziwe. Biorąc pod uwagę , NP również trudno jest zdecydować, czy jakieś słowo wejściowe jest w ponieważ muszę sprawdzić, czy przypisanie daje jako wyjście, ale łatwo jest znaleźć jakieś słowo w , oceniając obwód na dowolnym dowolnym wejściu).w L L C ′ w L w $C$$w$$L$$L$$C'$$w$$L$$w$$L$

Wskażę proste połączenie z niedeterministycznymi obwodami i krótko skomentuję twardość kryptograficzną.

W przypadku zdefiniuj złożoność obrazu, oznaczoną , jako minimalną liczbę bramek w dowolnym (fanin-dwa, AND / OR / NOT) obwodzie boolowskim , którego obraz jest . Pytanie dotyczy złożoności obliczeń , biorąc pod uwagę tabelę prawdy reprezentującą (ciąg długości ). i m c ( S ) C : { 0 , 1 } m → { 0 , 1 } n S i m c ( S ) S 2 $S \subseteq \{0, 1\}^n$$imc(S)$$C: \{0, 1\}^m \rightarrow \{0, 1\}^n$$S$$imc(S)$$S$$2^n$

Ponadto określenie niedeterministycznych obwodu złożoność z , który we''ll oznaczają , w zależności od obwodu najmniejszego niedeterministycznych przyjmowania dokładnie . Oznacza to, że wymagamy od aby iff . Jest to standardowe pojęcie używane do zdefiniowania niejednorodnej klasy : jest to klasa wszystkich zbiorów , z , takie jak .n c c ( S ) C ( x , y ) : { 0 , 1 } n + m ′ → { 0 , 1 } S C x ∈ S ∃ y : C ( x , y ) = 1 N P / p o l y S = { S n } n > $S$$ncc(S)$$C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$$S$$C$$x \in S$$\exists y: C(x, y) = 1$$NP/poly$$S = \{S_n\}_{n > 0}$ n c c ( S n ) ≤ p o l y ( n $S_n \subseteq \{0, 1\}^n$$ncc(S_n) \leq poly(n)$

Chciałem zwrócić uwagę, że . Oba kierunki tej nierówności są łatwe do zweryfikowania. $imc(S) = ncc(S) \pm O(n)$

Niech oznacza deterministyczną złożoność obwodu. Korzystając z Razborova-Rudicha, artykuł, o którym wspomina Dai Le (z grubsza mówiąc tutaj), że przy pewnych założeniach kryptograficznych trudno jest pod względem obliczeniowym odróżnić tabele prawdy z małe od tabel prawdy naprawdę losowych ( z wartością prawie maksymalną). Losowe ma również prawie maksymalne, a my oczywiście mamy . Twój problem jest więc trudny przy tych samych założeniach.$dcc(S)$d c c ( S ) S d c c ( S ) S n c c ( S ) n c c ( f ) ≤ d c c ( f $S$$dcc(S)$$S$$dcc(S)$$S$$ncc(S)$$ncc(f) \leq dcc(f)$

Które jest trudniejsze do obliczenia, biorąc pod uwagę tabelę prawdy dla , lub ? Czy istnieje jakakolwiek obniżka? Nie wiemd c c ( S ) n c c ( S $S$$dcc(S)$$ncc(S)$

Powinieneś rzucić okiem na ten artykuł Kabanetsa i Cai. Zacytuję streszczenie artykułu:

Badamy złożoność problemu minimalizacji obwodu: biorąc pod uwagę tabelę prawdy funkcji boolowskiej i parametru , decydujemy, czy może być zrealizowane przez obwód boolowski wielkości co najwyżej . Argumentujemy, dlaczego ten problem prawdopodobnie nie występuje w (a nawet w ), podając szereg zaskakujących konsekwencji takiego założenia. Twierdzimy również, że udowodnienie, że ten problem jest -kompletny (jeśli to rzeczywiście prawda), oznaczałoby udowodnienie silnych dolnych granic obwodu dla klasy , co wydaje się wykraczać poza obecnie znane techniki.s f s P P / p o l y N P $f$$s$$f$$s$$\mathsf{P}$$\mathsf{P}/\mathsf{poly}$$\mathsf{NP}$$\mathsf{E}$

Chociaż wspomniany obwód oblicza funkcję F : { 0 , 1 } m → L , możemy go traktować jako ciąg obwodów C ′ 1 , C ′ 2 , … , C ′ n , gdzie C ′ i oblicza bit wyjściowy . Ponieważ każde oblicza funkcję logiczną , minimalizując obwody$C'$$F:\{0,1\}^m \rightarrow L$$C'_1,C'_2,\ldots,C'_n$$C'_i$ F C ′ i { 0 , 1 } m → { 0 , 1 } C ′ $i^{\rm th}$$F$$C'_i$$\{0,1\}^m\rightarrow \{0,1\}$$C'_i$ wydaje się trudne według powyższego wyniku.