Czy

W ankiecie „Małe głębokości obwodów kwantowych” D. Bery, F. Greena i S. Homera (s. 36 z ACM SIGACT News, czerwiec 2007 t. 38, nr 2) przeczytałem następujące zdanie:

Klasyczna wersja (w której bramki i mają co najwyżej stały wentylator) jest wyraźnie słabsza niż .$QAC^0$$AND$$OR$$AC^0$

Brak odniesienia do tego roszczenia. Nazwę tę klasę , gdzie oznacza „ograniczony fanout”. (Zoo złożoności jest wyłączone i nie mogę zweryfikować, czy taka klasa ma już nazwę w literaturze). Jeśli założymy nieograniczony rozkład dla bitów wejściowych, wówczas obwód wydaje się być równoważny formułom stałej głębokości do wielomianowego wzrostu rozmiaru, więc powyższe twierdzenie nie ma sensu. Zamiast tego, jeśli założymy również ograniczenie fanoutu dla bitów wejściowych, nie mogę wymyślić żadnego języka, który oddziela tę klasę od . Możliwym kandydatem może być język , tzn . język ciągów tylko z jednym 1. Łatwo jest pokazać$AC^0_{bf}$$bf$ X : = { x | waga ( x ) = 1 } X ∈ A C 0 X ∉ A C 0 b $AC^0$$X := \{x | \mbox{weight}(x) = 1 \}$$X \in AC^{0}$ , ale nie udało mi się udowodnić, że .$X \notin AC^{0}_{bf}$

Pytania są następujące:

Czy rzeczywiście słabszy niż ? Jeśli tak, jakiś pomysł lub odniesienie do tego, jak to udowodnić? A jaki jest język, który dzieli te dwie klasy? Co z ? A C 0$AC^0_{bf}$$AC^0$$X$

Ograniczenie wentylacji bitów wejściowych i bramek sprawi, że rozmiar obwodu będzie liniowy. Niech będzie ograniczeniem na wachlowaniu bram i wejść. Jest to DAG z maksymalnym stopniem wyjścia ograniczonym przez k i maksymalną ścieżką długości d . Liczba dostępnych drutów na każdym poziomie może wzrosnąć k razy, a liczba dostępnych drutów u góry wynosi k n , więc całkowita liczba drutów w obwodzie wynosi co najwyżej k n ∑ d i = 0 k i ≤ k d + 1 n, co oznacza O ( n ) .$k$$k$$d$$k$$kn$$kn \sum_{i=0}^d k^i \leq k^{d+1} n$$O(n)$

Każda funkcja która wymaga wielkości nieliniowej, oddzieli klasę funkcji z ograniczonym rozkładem (zastosowanym również do bitów wejściowych) od A C 0 . Oto kilka przykładów:$\mathsf{AC^0}$$\mathsf{AC^0}$

1. [CR96]: AN C 0 funkcja wielkości potrzeba bardzo liniowa jest 1$\mathsf{AC^0}$ - przybliżony selektor$\frac{1}{4}$. A - przybliżony selektor to dowolna funkcja, której wartość to:$\frac{1}{4}$

   • za każdym razem, gdy liczba 1 s wynosi co najwyżej$0$$1$ ,$\frac{n}{4}$
   • za każdym razem, gdy liczba 0 s wynosi co najwyżej$1$$0$ ,$\frac{n}{4}$
   • w przeciwnym razie może być lub 1 .$0$$1$

2. [Ros08] wykazuje, że -clique ma C 0 funkcje złożoność n Θ ( k ) ( n 2 bity wejściowe są możliwe krawędzie wykresu z n wierzchołków). Daje to super-mniejszy rozmiar linii dla k > 2 .$k$$\mathsf{AC^0}$$n^{\Theta(k)}$$n^2$$n$$k\gt 2$

3. Prawdopodobnie możliwe jest uogólnienie przykładu w puszce 2 na istnienie dowolnej nietrywialnej (wymagającej więcej niż jednego bitu) stałej indukowanej podbudowy w danej nieuporządkowanej strukturze, np .:

   • istnienie ścieżki o długości 2 na danym wykresie,
   • ,$\#_1(x)=2$

   since they require super constant number of gates depending on a bit which is not possible in $\mathsf{AC^0_{bf}}$.

4. The easiest example is a duplicator gate, i.e. a gate that creates $\omega(1)$ copies of its input bit. This is not possible in $\mathsf{AC^0_{bf}}$ since only $O(1)$ of gates can depend on each input bit.

Również dowolny obwód o rozmiarze S można przekształcić w wzór o wielkości co najwyżej k d S, a zatem ma wzór A C 0 b f o rozmiarze k 2 d + 1 n, więc dowolna funkcja superlinearna A C 0 złożoność formuły nie będzie w A C 0 b f .$\mathsf{AC^0_{bf}}$$S$$k^dS$$\mathsf{AC^0_{bf}}$$k^{2d+1}n$$\mathsf{AC^0}$$\mathsf{AC^0_{bf}}$

Referencje:

[CR96] S. Chaudhuri i J. Radhakrishnan, „ Deterministic Restrictions in Circuit Complexity ”, 1996

[Ros08] Benjamin Rossman, "On the Constant-Depth Complexity of k-Clique", 2008

[Juk] Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", draft