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$ $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 ? $AC^0_{bf}$ $AC^0$ $X$

cc.complexity-theory circuit-complexity

— Alessandro Cosentino
źródło

Ograniczenie wentylacji bitów wejściowych spowoduje, że obwód będzie miał rozmiar liniowy. Każdy

funkcją wielkości wymaga bardzo liniową je rozdzielić.

A C^{0}

$AC^0$

— Kaveh

@Kaveh: Może mógłbyś odśwież że jako odpowiedź, a być może przykład wyraźnej funkcji, która wymaga super-size liniowy

obwodów i być może odniesienia, który pokazuje wielkość dolna granica? (Lub dołącz argument do swojej odpowiedzi, jeśli jest to bardzo prosty?)

A C^{0}

$AC^0$

— Robin Kothari

@Kaveh Dziękuję. Nie wiedziałem, że znany jest rozdział między obwodami o stałej głębokości

i wielkości liniowej (najwyraźniej zwany

). Odniesieniem jest „Deterministyczne ograniczenia w złożoności obwodu” autorstwa S. Chaudhuri i J. Radhakrishnana. @Kaveh Czy umiesz zamieścić komentarz w odpowiedzi?

A C^{0}

$AC^0$

L C^{0}

$LC^0$

— Alessandro Cosentino,

Jak omówiono w pytaniu uzupełniającym cstheory.stackexchange.com/questions/7447/... ,

jest takie samo jak formuła wielkości liniowej.

A C_{b f}^{0}

$AC^0_{bf}$

— domotorp

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 i maksymalną ścieżką długości . Liczba dostępnych drutów na każdym poziomie może wzrosnąć razy, a liczba dostępnych drutów u góry wynosi , więc całkowita liczba drutów w obwodzie wynosi co najwyżej co oznacza . $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 . Oto kilka przykładów: $\mathsf{AC^0}$ $\mathsf{AC^0}$

[CR96]: AN funkcja wielkości potrzeba bardzo liniowa jest $\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 s wynosi co najwyżej $0$ $1$ , $\frac{n}{4}$
- za każdym razem, gdy liczba s wynosi co najwyżej $1$ $0$ , $\frac{n}{4}$
- w przeciwnym razie może być lub . $0$ $1$
[Ros08] wykazuje, że -clique ma funkcje złożoność ( bity wejściowe są możliwe krawędzie wykresu z wierzchołków). Daje to super-mniejszy rozmiar linii dla . $k$ $\mathsf{AC^0}$ $n^{\Theta(k)}$ $n^2$ $n$ $k\gt 2$
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}}$ .
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 można przekształcić w wzór o wielkości co najwyżej a zatem ma wzór o rozmiarze więc dowolna funkcja superlinearna złożoność formuły nie będzie w . $\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

— Kaveh
źródło

A more recent separation between

L C^{0}

$LC^0$ and

A C^{0}

$AC^0$ follows from this result due to Benjamin Rossman. He shows that for all constant

k

$k$ (also some growing

k

$k$ ) and constant

d

$d$ , any depth

d

$d$ circuit for

k

$k$ -clique on an

n

$n$ vertex graph must have size

Ω (n^{k / 4})

$\Omega(n^{k/4})$ . This implies that the hierarchy of languages accepted by

A C^{0}

$AC^0$ circuits of size

n^{k}

$n^k$ (for different

k

$k$ ) is actually infinite.

— Srikanth

I updated the answer, thanks to Alessandro, domotorp, Robin, Srikanth, and Stasys.

— Kaveh

@Kaveh: Alright, thanks. If you do find a way to tweak Rossman's result, I'll be interested to hear it. As for the threshold-2 function, I think we can show it's not in this class by noting that all functions in this class have linear-sized formulae, and threshold-2 has a formula size lower bound of

Ω (n \log n)

$\Omega(n \log n)$ .

— Robin Kothari

@Kaveh: If by

P_{k}

$P_k$ , you mean the path of length

k

$k$ , you should keep in mind that there are

A C^{0}

$AC^0$ circuits of size

2^{k} n^{O (1)}

$2^kn^{O(1)}$ for these functions (this follows essentially from the Color Coding technique of Alon, Yuster, and Zwick). I am not sure Rossman's technique gives these sorts of bounds (though I don't know of any reason why it shouldn't).

— Srikanth

@Kaveh: I am sorry, I should have provided a reference. The paper you point out initiated the Color coding method for finding paths and other subgraphs quickly. Amano, in this paper, was the first to point out that the algorithms could be implemented in

A C^{0}

$AC^0$ .

— Srikanth