Charakterystyka stałej głębokości

To pytanie dotyczy złożoności obwodu. (Definicje znajdują się na dole).

Yao Beigel-Tarui wykazała, że każdy rodziny obwód wielkość jest równoważny rodziny obwodu o rozmiarze głębokości dwóch , w którym brama wyjściowa jest funkcją symetryczną, a drugi etap składa od bramy $ACC^0$ $s$ $s^{poly(\log s)}$ $AND$ $poly(\log s)$ wachlarz. Jest to dość niezwykłe „załamanie głębokości” rodziny obwodów: z obwodu głębokości 100 można zmniejszyć głębokość do 2, z jedynie quasi-wielomianowym powiększeniem (i jedną fantazyjną, ale wciąż ograniczoną bramą u góry).

Moje pytanie: czy istnieje znany sposób wyrażenia rodziny obwodów , podobnie? Co bardziej ambitne, co z rodziną obwodów ? Potencjalne odpowiedzi miałyby postać: „Każdy obwód o rozmiarze może zostać rozpoznany przez rodzinę wielkości o głębokości drugiej , gdzie bramka wyjściowa jest funkcją typu a drugi poziom bram ma typ ” . $TC^0$ $NC^1$ $TC^0$ $s$ $f(s)$ $X$ $Y$

Nie musi to być druga głębokość, każdy wynik o stałej głębokości byłby interesujący. Bardzo interesujące byłoby udowodnienie, że każdy obwód może być reprezentowany na głębokości 3 przez obwód składający się tylko z bramek funkcji symetrycznych. $TC^0$

Kilka drobnych spostrzeżeń:

Jeśli odpowiedź jest trywialne dla każdej logicznej funkcji (możemy wyrazić dowolny funkcję jak w s). Dla konkretności wymagamy . $f(n)=2^n$ $OR$ $2^n$ $AND$ $f(n) = 2^{n^{o(1)}}$
Odpowiedź jest trywialna, jeśli lub mogą być dowolną funkcją obliczalną w ... :) Oczywiście interesują mnie funkcje „prostsze”, cokolwiek to znaczy. Definiowanie tego jest trochę śliskie, ponieważ istnieją rodziny funkcji symetrycznych, których nie można obliczyć. (Są jedne języki, których nie da się obliczyć.) Jeśli chcesz, możesz po prostu zastąpić i funkcjami symetrycznymi w instrukcji, jednak byłbym zainteresowany innymi porządnymi wyborami bramek. $X$ $Y$ $TC^0$ $X$ $Y$

(Teraz krótkie przypomnienie notacji:

$ACC^0$ $AND$ $OR$ $MOD_m$ $m > 1$ $MOD_m$ $1$ $m$

$TC^0$ $MAJORITY$

$NC^1$ $AND$ $OR$ $NOT$

$ACC^0 \subseteq TC^0 \subseteq NC^1$

cc.complexity-theory circuit-complexity upper-bounds

— Ryan Williams
źródło

k

$k$

k + 1

$k+1$

T C^{0}

$TC^0$

T C^{0}

$TC^0$

N C^{1}

$NC^1$

Ryan, nie widzę, jakiej odpowiedzi tutaj szukasz. Jeśli tak naprawdę mówisz o bramkach symetrycznych, to (ponieważ można je symulować większością na głębokości drugiej), twoje pytanie jest równoważne zapadnięciu się TC0 do stałej głębokości (być może z pewnym niewielkim super-wielomianowym wzrostem wielkości) - dobrze znanym otwarty problem. Jeśli chcesz „rozluźnić” symetrię, to wynik Barringtona wydaje się tak dobry, jak możesz oczekiwać?

— Noam

@Noam: Chciałbym sprawdzić, czy są jakieś inne interesujące odpowiedzi; jeśli nie, oddam 300 Lance'owi. Istnieją również pośrednie możliwości, np. Obwody głębokości trzy z funkcją symetryczną na wyjściu, ale niekoniecznie symetryczną na pozostałych dwóch warstwach. W każdym razie, nakłonienie cię do zastanowienia się przez 5 minut jest już warte 300 nagród.

— Ryan Williams

A teraz (po 8 listopada) znamy pochodzenie tego pytania ...

— slimton,

$TC^0$ $AC^0$ $TC^0$ $A$ $TC^0$ $f$ $\sharp AC^0$ $k$

$x \in A$ $f(x) = 2^{|x|^k}$

$\sharp AC^0$ $Z$ $x_i$ $1-x_i$

Biorąc pod uwagę, że, jak zauważa Boaz w swojej odpowiedzi, istnieje niebanalna redukcja głębokości dla obwodów arytmetycznych, może to być coś do rozważenia.

— Kristoffer Arnsfelt Hansen
źródło

$NC^1$

— Lance Fortnow
źródło

Zgadzam się, że twierdzenie Barringtona sugeruje tutaj coś interesującego. Ale ta bramka wyjściowa jest bardzo „niesymetryczną” funkcją :)

— Ryan Williams,

Właściwie wydaje się, że masz obwód głębokości 1 ... Reprezentując permutację jako (powiedzmy) macierz boolowską 5x5, jest to tylko rzut na bramę mnożenia permutacji.

— Noam

$f:{0,1}^n\rightarrow{0,1}^n$ $O(\log n)$ $O(n)$ $g$ $NC_0[n^{\epsilon}]$ $f$ $2^{n-o(n)}$ $f$ $g$ $NC^1$

— Boaz Barak
źródło

T C^{0}

$TC^0$

O (n / (ε \log \log n))

$O(n/(\varepsilon \log \log n))$

ε \log n

$\varepsilon \log n$

g

$g$

f

$f$

Kristoffer, czy możesz dodać link jako osobną odpowiedź? Dzięki!

— Ryan Williams

o (n)

$o(n)$

n^{ϵ}

$n^{\epsilon}$

2^{n - o (n)}

$2^{n-o(n)}$