Obwody arytmetyczne z tylko jedną bramką progową

Gdy ogranicza się do wejść - , każdy -circuit oblicza jakąś funkcję . Aby uzyskać funkcję logiczną , możemy po prostu dodać jedną bramkę progową fanin-1 jako bramkę wyjściową. Na wejściu wynikowy próg - obwód wyprowadza następnie jeśli , i wyprowadza jeśli ; próg może być dowolną liczbą całkowitą dodatnią, która może zależeć od $0$ $1$ $\{+,\times\}$ $F(x_1,\ldots,x_n)$ $F:\{0,1\}^n\to \mathbb{N}$ $a\in\{0,1\}^n$ $\{+,\times\}$ $1$ $F(a)\geq t$ $0$ $F(a)\leq t-1$ $t=t_n$ $n$ ale nie na wartościach wejściowych. Powstały obwód oblicza pewną (monotoniczną) funkcję boolowską . $F':\{0,1\}^n\to \{0,1\}$

Pytanie: Czy progi -obwody mogą być skutecznie symulowane przez -circuits? $\{+,\times\}$ $\{\lor,\land\}$

Pod „wydajnie” mam na myśli „z wielomianowym wzrostem wielkości”. Odpowiedź brzmi „tak” dla progu : wystarczy zastąpić przez , przez i usunąć ostatnią bramkę progową. Oznacza to, że -obwody są w rzeczywistości progiem -obwody. Ale co z większymi progami, powiedzmy, ? $t=1$ $+$ $\lor$ $\times$ $\land$ $\{\lor,\land\}$ $1$ $\{+,\times\}$ $t=2$

Można zdefiniować arytmetyczne analogi większości klas obwodów boolowskich po prostu używając zamiast OR, zamiast AND i zamiast . Na przykład, obwody to -obwody o stałej głębokości z nieograniczonymi bramkami fanin i oraz wejściami i . Agrawal, Allender i Datta wykazały, że ten próg = . (Przypomnij sobie, że sam jest poprawny $\#C$ $C$ $+$ $\times$ $1-x_i$ $\bar{x}_i$ $\#AC^0$ $\{+,\times\}$ $+$ $\times$ $x_i$ $1-x_i$ $\#AC^0$ $TC^0$ $AC^0$ podzbiór ; weźmy, powiedzmy, funkcję większości). Innymi słowy, obwody progowe o stałej głębokości można skutecznie symulować za pomocą obwodów o stałej głębokości , z tylko jedną bramą progową! Zauważ jednak, że moje pytanie dotyczy obwodów monotonicznych (bez minusów „ ” jako bramek, a nawet bez jako wejść). Czy w takim razie jedna (ostatnia) brama progowa może być tak potężna? Nie znam tego, więc wszelkie powiązane wskazówki są mile widziane. $TC^0$ $\{+,-,\times\}$ $-$ $1-x_i$

Uwaga: istnieje jeszcze inny interesujący wynik związany z Arnoldem Rosenbloomem: obwody z tylko jedną funkcją monotoniczną ponieważ bramka wyjściowa może obliczyć każdą funkcję wycinka za pomocą bramek . Funkcja wycinka jest monotoniczną funkcją logiczną, która dla niektórych ustalonych wartości wyprowadza (odpowiednio ) na wszystkich wejściach z mniejszą liczbą (odpowiednio, więcej) niż . Z drugiej strony, łatwe liczenie pokazuje, że większość funkcji wycinania wymaga ogólnych -obwodów o wykładniczej wielkości. Zatem jedna „niewinna” dodatkowa bramka wyjściowa może $\{+,\times\}$ $g:\mathbb{N}^2\to\{0,1\}$ $O(n)$ $k$ $0$ $1$ $k$ $\{\lor,\land,\neg\}$ uczyń obwody monotoniczne wszechmocnymi! Moje pytanie dotyczy tego, czy może się tak zdarzyć, gdy jest bramą progową dla fanin- . $g:\mathbb{N}\to\{0,1\}$ $1$

AKTYWIZACJA (dodano 03.11.2014): Emil Jeřábek pokazał (poprzez zadziwiająco prostą konstrukcję, patrz jego odpowiedź poniżej), że odpowiedź brzmi „tak”, o ile dla stałej . Pytanie pozostaje otwarte tylko dla progów wielomianowych (w ).

t \leq n^{c}

$t\leq n^c$

c

$c$

n

$n$

Zwykle w aplikacjach działają tylko duże progi: zwykle potrzebujemy progów w postaci dla . Powiedzmy, że jeśli zlicza liczbę ścieżek - na wykresie określonych przez wejście - , to dla o The threshold- wersja rozwiązuje istnienie Hamiltona - problemu ścieżki na wykresy -Vertex (patrz, na przykład tutaj ). $2^{n^{\epsilon}}$ $\epsilon > 0$ $F:\{0,1\}^n\to \mathbb{N}$ $s$ $t$ $0$ $1$ $t=m^{m^2}$ $m\approx n^{1/3}$ $t$ $F$ $s$ $t$ $m$

(Dodano 14.11.2014): Ponieważ Emil odpowiedział na dużą część mojego pytania, a ponieważ sprawa progów wykładniczych nie jest widoczna, teraz akceptuję (bardzo miłą) odpowiedź Emila.

circuit-complexity arithmetic-circuits cc-complexity-theory

— Stasys
źródło

Poczekaj… wykładniczy rozmiar? Myślę, że można zaimplementować funkcję plasterka w rozmiarze wielomianowym za pomocą bramek boolowskich, to tylko formuła (która nie może ponownie użyć wyników pośrednich więcej niż jeden raz), która musi mieć wielkość wykładniczą.

— Zsbán Ambrus

@ Zsbán Ambrus: Istnieje co najwyżej obwód o rozmiarze , ale co najmniej różne funkcje slice już dla ; a, b dodatnie stałe.

S^{a S}

$S^{aS}$

S

$S$

2^{2^{b n}}

$2^{2^{bn}}$

k

$k$

k = n / 2

$k=n/2$

— Stasys

Próg 2, a bardziej ogólnie progi ograniczone przez , można skutecznie symulować wykonując obliczenia w trakcie semirowania .

2^{n^{c}}

$2^{n^c}$

({0, \dots, t}, min {x + y, t}, min {x y, t})

$(\{0,\dots,t\},\min\{x+y,t\},\min\{xy,t\})$

— Emil Jeřábek wspiera Monikę

Otrzymujesz obwody bezpośrednio. Wymienić każdy węzeł z węzłów , gdzie oblicza logiczny źródłowe . (Nie potrzebujesz ponieważ oblicza stałą , ale upraszcza to poniższe wyrażenie.) W tej reprezentacji i można symulować za pomocą obwodów o rozmiarze : np. jeśli , to .

\land, \lor

$\land,\lor$

c

$c$

t + 1

$t+1$

c_{0}, \dots, c_{t}

$c_0,\dots,c_t$

c_{i}

$c_i$

c \geq i

$c\ge i$

c_{0}

$c_0$

1

$1$

+

$+$

\cdot

$\cdot$

{\land, \lor}

$\{\land,\lor\}$

O (t^{2})

$O(t^2)$

c = a + b

$c=a+b$

c_{i} = \underset{j + k \geq i}{⋁} (a_{j} \land b_{k})

$c_i=\bigvee_{j+k\ge i}(a_j\land b_k)$

— Emil Jeřábek wspiera Monikę

@Emil Jeřábek: Very nice! Dodałem teraz uwagę na ten temat. Właściwie może warto postawić ten komentarz jako odpowiedź: przypadek progu wielomianowego również nie był od razu jasny (przynajmniej dla mnie).

— Stasys

Odpowiedź brzmi „tak”, jeśli . Mówiąc bardziej ogólnie, próg obwód o rozmiarze z progiem może być symulowany przez obwód o rozmiarze . $t=n^{O(1)}$ $\{+,\cdot\}$ $s$ $t$ $\{\lor,\land\}$ $O(t^2s)$

Najpierw zauważ, że wystarczy ocenić obwód w z obciętym dodawaniem i mnożeniem: w szczególności, jeśli , to i również, lub . $\{0,\dots,t\}$ $a,a'\ge t$ $a+b,a'+b\ge t$ $ab,a'b\ge t$ $ab=a'b(=0)$

Mając to na uwadze, możemy zasymulować obwód z logicznym obwodem monotonicznym, zastępując każdy węzeł węzłami , gdzie ma obliczyć predykat . (Potrzebujemy tylko dla wygody notacji, to oblicza funkcję stałej ) Jeśli jest boolowską zmienną wejściową , przyjmujemy , . Jeśli jest bramą dodawania, powiedzmy , implementujemy ją poprzez Bramki mnożenia są obsługiwane w ten sam sposób. $c$ $c_0,\dots,c_t$ $c_i$ $c\ge i$ $c_0$ $1$ $c$ $x$ $c_1=x$ $c_2=\dots=c_t=0$ $c$ $c=a+b$

c_{i} = \underset{\begin{matrix} j, k \leq t \\ j + k \geq i \end{matrix}}{⋁} (a_{j} \land b_{k}) .

$c_i=\bigvee_{\substack{j,k\le t\\j+k\ge i}}(a_j\land b_k).$

Wymaga to bramek na jedną bramkę oryginalnego obwodu. Jako drobną optymalizację możemy zredukować ją do , wprowadzając dzięki czemu każdy jest używany jako dane wejściowe tylko jednego z bramy. $O(t^3)$ $O(t^2)$

\begin{aligned} c_{t} & = \underset{j + k \geq t}{⋁} (a_{j} \land b_{k}), \\ c_{i} & = c_{i + 1} \lor \underset{j + k = i}{⋁} (a_{j} \land b_{k}), i < t, \end{aligned}

$\begin{align*} c_t&=\bigvee_{j+k\ge t}(a_j\land b_k),\\ c_i&=c_{i+1}\lor\bigvee_{j+k=i}(a_j\land b_k),\qquad i<t, \end{align*}$

a_{j} \land b_{k}

$a_j\land b_k$

c_{i}

$c_i$

— Emil Jeřábek wspiera Monikę
źródło