Классы случайности и сложности малых схем

Пусть некоторый класс сложности и быть рандомизированное аналог определяется как по отношению к . Более формально мы предоставляем полиномиально много случайных битов и принимаем входные данные, если вероятность принять больше $\mathcal{C}$ $\textrm{BP-}\mathcal{C}$ $\mathcal{C}$ $\textrm{BPP}$ $\textrm{P}$ . $\frac{2}{3}$

Известно, что для класса неоднородных цепей : $\textrm{BPAC}^0=\textrm{AC}^0$

Миклош Айтай, Майкл Бен-Ор: теорема о вероятностных вычислениях постоянной глубины STOC 1984: 471-474

Известны ли обобщения этой теоремы? Например, знаем ли мы, что (все еще в неоднородной настройке)? Этот последний вопрос , кажется , как - то нетривиально мне так кажется правдоподобным , что, например , в . $\mathrm{BPNC}^1=\mathrm{NC}^1$ $s,t\textrm{-Connectivity}$ $\textrm{BPNC}^1$

Соответствующий пост на эту тему: /mathpro/35184/use-of-randomness-in-constant-parallel-time

circuit-complexity randomized-algorithms CP
источник

Что заставляет вас задуматься о подключении?

Михаэль Кадилхак

Вы спрашиваете о единообразных классах цепей? Совершенно очевидно, что неоднородные классы типа

замкнуты относительно оператора BP.

N C^{1}

$\mathrm{NC^1}$

Эмиль Йержабек

Просто используйте тот же аргумент, что и для P / poly. Вам нужна только мажоритарная функция, которая определяется в

. (Айтаю и Бен-Ору нужно больше работать, так как большинство не доступно в

)

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

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

A C^{0}

$\mathrm{AC^0}$

Эмиль Йержабек

@ EmilJeřábek Вы совершенно правы. Для каждого не-unifom класса схемы выше

мы имеем

. Большое спасибо.

{TC}^{0}

$\textrm{TC}^0$

BP - C = C

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

СР

@ EmilJeřábek: Ах, я вижу. Я думаю, что это граница; это, очевидно, не вопрос исследования , но он был задан всерьез кем-то, имеющим сложный исследовательский опыт, который был просто введен в заблуждение, пытаясь расширить Аджтай-Бен-Ор, а не использовать более простой подход.

Джошуа

Ответы:

Большинство классов неоднородной сложности, в том числе , закрываются под оператором тем же аргументом, что и : используя границу Черноффа – Хеффдинга, вероятность ошибки может быть уменьшена ниже путем запуска экземпляров схемы с независимыми случайными битами параллельно и получения большинства голосов; затем по границе объединения последовательность случайных битов дает правильный результат для всех входов длины $\mathrm{NC^1}$ $\mathrm{BP}$ $\mathrm{BPP\subseteq P/poly}$ $2^{-n}$ $O(n)$ $2^n$ $n$ одновременно с ненулевой вероятностью и, в частности, существует такая последовательность. Мы можем встроить его в схему.

Этот аргумент применяется к любому классу цепей, который замкнут при взятии большинства параллельных копий схемы и фиксации входных вентилей к константам. На практике это означает любой приличный неоднородный класс выше , так как большинство вычислимо в . $O(n)$ $\mathrm{TC^0}$ $\mathrm{TC^0}$

Доказательство более сложное для , потому что этот класс не вычисляет мажоритарную функцию. (Хотя я не видел бумаги Ajtai и Ben-Or, я предполагаю, что они используют какое-то приблизительное большинство.) $\mathrm{AC^0}$

Эмиль Йержабек
источник