Classes de aleatoriedade e complexidade de pequenos circuitos

Vamos ser uma classe de complexidade e ser o homólogo randomizado de definida como com respeito ao . Mais formalmente, fornecemos polinomialmente muitos bits aleatórios e aceitamos uma entrada se a probabilidade de aceitação for superior a $\mathcal{C}$ $\textrm{BP-}\mathcal{C}$ $\mathcal{C}$ $\textrm{BPP}$ $\textrm{P}$ . $\frac{2}{3}$

Sabe-se que para a classe de circuitos não uniformes temos : $\textrm{BPAC}^0=\textrm{AC}^0$

Miklós Ajtai, Michael Ben-Or: um teorema das computações probabilísticas de profundidade constante STOC 1984: 471-474

As generalizações desse teorema são conhecidas? Por exemplo, sabemos se (ainda na configuração não uniforme)? Esta última questão parece de alguma forma não trivial para mim desde que parece plausível que, por exemplo, está em . $\mathrm{BPNC}^1=\mathrm{NC}^1$ $s,t\textrm{-Connectivity}$ $\textrm{BPNC}^1$

Uma publicação relevante sobre o assunto: /mathpro/35184/use-of-randomness-in-constant-parallel-time

circuit-complexity randomized-algorithms CP
fonte

O que impulsiona seu palpite sobre conectividade?

Michaël Cadilhac

Você está perguntando sobre aulas de circuito uniformes ? É bastante óbvio que classes não uniformes como

são fechadas sob o operador BP.

N C^{1}

$\mathrm{NC^1}$

Emil Jerabek

Basta usar o mesmo argumento que para P / poli. Você só precisa da função majoritária, que é definível em

. (Ajtai e Ben-Or precisam de mais trabalho como a maioria é não disponível em

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

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

A C^{0}

$\mathrm{AC^0}$

Emil Jerabek

@ EmilJeřábek você está perfeitamente certo. Para cada classe de circuito não-unifom acima

temos

. Muito obrigado.

{TC}^{0}

$\textrm{TC}^0$

BP - C = C

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

@ EmilJeřábek: Ah, entendo. Eu acho que é limítrofe; obviamente não é uma questão de pesquisa , mas foi claramente perguntado com sinceridade por alguém com alguma experiência em pesquisa em complexidade, que foi simplesmente enganado ao tentar estender Ajtai-Ben-Or em vez de usar uma abordagem mais direta.

Joshua Grochow 13/03/19

A maior complexidade não uniforme classes: -incluído são fechados sob o operador pelo mesmo argumento como : usando o Chernoff-Hoeffding ligado, a probabilidade de erro pode ser reduzido abaixo de executando instâncias do circuito com bits aleatórios independentes em paralelo e obtendo uma votação majoritária; então, pelo limite de união, uma sequência de bits aleatórios fornece o resultado correto para todas as entradas de comprimento $\mathrm{NC^1}$ $\mathrm{BP}$ $\mathrm{BPP\subseteq P/poly}$ $2^{-n}$ $O(n)$ $2^n$ $n$ simultaneamente com probabilidade diferente de zero e, em particular, existe essa sequência. Podemos conectá-lo ao circuito.

Esse argumento se aplica a qualquer classe de circuitos fechados sob a maioria das cópias paralelas de de um circuito e fixando as portas de entrada para constantes. Na prática, isso significa qualquer classe não uniforme decente acima de , pois a maioria é computável em . $O(n)$ $\mathrm{TC^0}$ $\mathrm{TC^0}$

A prova é mais complicada para , porque essa classe não calcula a função majoritária. (Embora eu não tenha visto o jornal Ajtai e Ben-Or, acho que eles usam algum tipo de maioria aproximada.) $\mathrm{AC^0}$

Emil Jeřábek
fonte

Classes de aleatoriedade e complexidade de pequenos circuitos

Respostas: