Klasy złożoności losowości i małych obwodów

Niech będzie klasą złożoności, a będzie losowym odpowiednikiem zdefiniowanego jako w odniesieniu do . Bardziej formalnie podajemy wielomianowo wiele bitów losowych i akceptujemy dane wejściowe, jeśli prawdopodobieństwo akceptacji jest większe niż . $\mathcal{C}$ $\textrm{BP-}\mathcal{C}$ $\mathcal{C}$ $\textrm{BPP}$ $\textrm{P}$ $\frac{2}{3}$

Wiadomo, że dla klasy obwodów nierównomiernych mamy : $\textrm{BPAC}^0=\textrm{AC}^0$

Miklós Ajtai, Michael Ben-Or: Twierdzenie o probabilistycznych obliczeniach stałej głębokości STOC 1984: 471-474

Czy znane są uogólnienia tego twierdzenia? Na przykład, czy wiemy, czy (wciąż w nierównomiernym ustawieniu)? To ostatnie pytanie wydaje mi się nie trywialne, ponieważ wydaje się prawdopodobne, że na przykład znajduje się w . $\mathrm{BPNC}^1=\mathrm{NC}^1$ $s,t\textrm{-Connectivity}$ $\textrm{BPNC}^1$

Odpowiedni post na ten temat: /mathpro/35184/use-of-randomness-in-constant-parallel-time

circuit-complexity randomized-algorithms CP
źródło

Co napędza twoje przeczucie co do łączności?

Michaël Cadilhac,

Czy pytasz o jednolite klasy obwodów? Jest dość oczywiste, że nierównomierne klasy, takie jak

są zamknięte pod operatora BP.

N C^{1}

$\mathrm{NC^1}$

Emil Jeřábek

Wystarczy użyć tego samego argumentu, co w przypadku P / poly. Potrzebujesz tylko funkcji większości, którą można zdefiniować w

. (Ajtai i Ben-Or potrzebują więcej pracy, ponieważ większość nie jest dostępna w

T C^{0} \subseteq N C^{1}

$\mathrm{TC^0\subseteq NC^1}$

A C^{0}

$\mathrm{AC^0}$

Emil Jeřábek

@ EmilJeřábek masz całkowitą rację. Dla każdej klasy non-UNIFOM obwodu powyżej

mamy

. Dziękuję Ci bardzo.

{TC}^{0}

$\textrm{TC}^0$

BP - C = C

$\textrm{BP}-\mathcal{C}=\mathcal{C}$

@ EmilJeřábek: Ach, rozumiem. Myślę, że to granica; to oczywiście nie jest pytanie badawcze , ale zostało wyraźnie zadane poważnie przez kogoś z pewnym doświadczeniem badawczym w złożoności, który został po prostu wprowadzony w błąd, próbując rozszerzyć Ajtai-Ben-Or, zamiast stosować bardziej proste podejście.

Joshua Grochow

Większość niejednorodnych klas złożoności - w tym - jest zamykanych pod operatorem przez ten sam argument, co : przy użyciu granicy Chernoffa-Hoeffdinga prawdopodobieństwo błędu można zmniejszyć poniżej przez równoległe prowadzenie wystąpień obwodu z niezależnymi losowymi bitami i głosowanie większością; następnie przez związanie, sekwencja losowych bitów daje poprawny wynik dla wszystkich danych wejściowych o długości $\mathrm{NC^1}$ $\mathrm{BP}$ $\mathrm{BPP\subseteq P/poly}$ $2^{-n}$ $O(n)$ $2^n$ $n$ jednocześnie z niezerowym prawdopodobieństwem, a w szczególności istnieje taka sekwencja. Możemy to podłączyć do obwodu.

Ten argument ma zastosowanie do dowolnej klasy obwodów, które są zamknięte, biorąc większość równoległych kopii obwodu i mocując bramki wejściowe do stałych. W praktyce oznacza to każdą przyzwoitą niejednorodną klasę powyżej , ponieważ większość można obliczyć w . $O(n)$ $\mathrm{TC^0}$ $\mathrm{TC^0}$

Dowód jest bardziej skomplikowany dla , ponieważ ta klasa nie oblicza funkcji większości. (Chociaż nie widziałem gazety Ajtai i Ben-Or, domyślam się, że używają oni w przybliżeniu większości). $\mathrm{AC^0}$

Emil Jeřábek
źródło

Klasy złożoności losowości i małych obwodów

Odpowiedzi: