Oszukiwanie

11

Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości.

Wiadomo, że -wise niezależności konieczne oszukać obwody głębokości , gdzie jest wielkości wejściowych. Jak można to udowodnić? $\log^{O(d)}(n)$ $AC^0$ $d$ $n$
Ponieważ powyższe jest prawdziwe, każdy generator pseudolosowy, który głupcy obwody głębokości musi koniecznie mieć długość nasion , co oznaczałoby, że nie można oczekiwać, aby udowodnić, przez PRG. Wierzę, że jest wciąż pytaniem otwartym, więc oznacza to, że trzeba użyć technik innych niż PRG, aby udowodnić $AC^0$ $d$ $l = \Omega(\log^d(n))$ $RAC^0 = AC^0$ $RAC^0 \stackrel{?}{=} AC^0$ . Uważam to za dziwne, ponieważ przynajmniej w przypadku , uważamy, że PRG są zasadniczojedynądrogą do odpowiedzi na to pytanie. $RAC^0 = AC^0$ $P \stackrel{?}{=} BPP$

Myślę, że brakuje mi czegoś naprawdę podstawowego.

— Społeczność
źródło

1

A C^{0}

$AC^{0}$

Właściwie nie jestem pewien, czy kiedykolwiek widziałem formalną wzmiankę o 1.) w jakiejkolwiek pracy itp., Ale wierzę, że jest to znane. Zobacz komentarz 29 autorstwa Scotta Aaronsona tutaj: scottaaronson.com/blog/?p=381

2

k = p o l y l o g (n)

$k = polylog(n)$

1

ok, teraz ma sens. Inne wyjaśnienie: czy wyrażenie „techniki derandomizacji inne niż PRG” ma sens? Czy PRG z definicji (przynajmniej w teorii złożoności) nie jest czymś, czego używamy do derandomizacji? @AbhishekBhrushundi: btw, podoba mi się pytanie. Dobrze jest wyjaśnić tego rodzaju rzeczy w cstheory ;-)

— Alessandro Cosentino

15

$k$ $k+1$ $(k+1)$ $k$ $k$ $n$ $d$ $\log^{d-1} n$

$k$ $O(\log n)$

— Manu
źródło

8

$AC^{0}$ $(n-1)$ $(n-1)$ $n$ $\epsilon$

$\log^{O(d)} n$ $AC^{0}$

— Ramprasad
źródło