obwodu

Czy wiadomo, czy problem z oceną obwodu występuje w ? Co powiesz na (uniform )? $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{ALogTime}$ $\mathsf{NC^1}$

Wiemy, że obwody o głębokości można oceniać za pomocą obwodów o głębokości gdzie jest stałą uniwersalną. Oznacza to, że obwody o głębokości można oceniać za pomocą obwodu o głębokości . Jednak nie zawiera funkcji, która ostatecznie dominuje nad wszystkimi funkcjami w . $k$ $k+c$ $c$ $k\lg n + o(\lg n)$ $O(\lg n)$ $O(\lg n)$ $O(\lg n)$

Wiemy, że problem oceny formuły występuje w . Każdy obwód jest równoważny formule boolowskiej. Czy nie możemy obliczyć rozszerzonej reprezentacji połączenia równoważnej formuły logicznej na podstawie danego obwodu w ? $\mathsf{ALogTime}$ $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{ALogTime}$

Przedłużonym reprezentacji połączenia obwodu zawiera

liczba bramek w obwodzie,
rodzaj każdej bramy, oraz
dla każdej bramki i każdej ścieżki w DAG obwodu brama osiągnęła z następującej ścieżki . $g$ $\pi$ $g$ $\pi$

Ścieżka jest podana w sekwencji 0/1, gdzie 0 oznacza przejście do lewego rodzica, a 1 oznacza przejście do prawego rodzica. Zauważ, że liczba ścieżek jest wielomianowa: długość ścieżek jest ograniczona głębokością obwodu.

cc.complexity-theory reference-request circuit-complexity Kaveh
źródło

O ile mi wiadomo, ocena nie jest znana w i przypuszcza się, że jest poza . Patrz „Teorie ograniczonej arytmetyki dla ”, E. Jerabek, Ann. Pure Appl. Logic 2011 ( math.cas.cz/~jerabek/papers/vnc.pdf ).

N C^{1}

$NC^1$

N C^{1}

$NC^1$

N C^{1}

$NC^1$

N C^{1}

$NC^1$

Iddo Tzameret

@IddoTzameret Może powinieneś zamienić komentarz w odpowiedź.

Dai Le

Co rozumiesz przez ocenę obwodu NC1? Czy masz na myśli, że dane wejściowe podane do oceniającego to obwód którego głębokość jest ograniczona przez dla pewnej stałej stałej , gdzie jest liczbą danych wejściowych do ?

C

$C$

c \log (n)

$c\log(n)$

c

$c$

n

$n$

C

$C$

Igor Shinkar

@Igor, dobra uwaga. Muszę przemyśleć i wyjaśnić.

Kaveh

@or, myślę, że możemy założyć, że głębokość obwodu wynosi dla dowolnej arbitralnej, ale stałej stałej ponieważ jest to trudne dla ramach redukcji .

c \lg n

$c \lg n$

c \geq 1

$c\geq 1$

N C^{1}

$\mathsf{NC^1}$

A C^{0}

$\mathsf{AC^0}$

Kaveh

O ile mi wiadomo, ocena nie jest znana z i przypuszcza się, że znajduje się poza . Widzieć $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{NC^1}$

Emil Jerabek, „ O teoriach ograniczonej arytmetyki dla $\mathsf{NC^1}$ ”, Ann. Pure Appl. Logika 2011

Iddo Tzameret
źródło

Dzięki Iddo. Patrzę na artykuł Emila i jest on bardzo pomocny. Stwierdza, że problem nie występuje w jeśli używamy bezpośredniej reprezentacji połączenia, ale jest w jeśli używamy rozszerzonej reprezentacji połączenia .

N C^{1}

$\mathsf{NC^1}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Następnie stwierdza, że następujący problem stanowi podstawową trudność obliczania ocena obwodu (z reprezentacją dc): Biorąc pod uwagę wykres skierowany na wierzchołków z ograniczonym out out, wierzchołki i liczba określają, czy jest osiągalne od co najwyżej kroków.

N C^{1}

$\mathsf{NC^1}$ $G$ $n$ $x,y \in G$ $d \leq \log n$ $y$ $x$ $d$

Kaveh

@Kaveh, możesz także spojrzeć na „Amplifikację dolnych granic przez środki samoodmienności” Allendera i Koucky'ego (JACM 2010). Podają również, że problem oceny nie jest znany w .

N C^{1}

$NC^1$

N C^{1}

$NC^1$

Iddo Tzameret

W rzeczywistości ta linia była inspiracją do mojego pytania. Uważam, że powinno być w jeśli użyjemy rozszerzonej reprezentacji połączenia, a papier Emila stwierdza, że tak jest.

N C^{1}

$\mathsf{NC^1}$

Kaveh

obwodu

Odpowiedzi: