O BPP vs. P é um problema real depois que sabemos que o BPP está no P / poly?

Nós sabemos (por agora cerca de 40 anos, obrigado Adleman, Bennet e Gill) que a inclusão BPP P / poli, e um ainda mais forte BPP / poli P / hold poli. O "/ poly" significa que trabalhamos de maneira não uniforme (um circuito separado para cada comprimento de entrada ), enquanto P sem esse "/ poly" significa que temos uma máquina de Turing para todos os comprimentos de entrada possíveis , ainda mais do que, digamos, = o número de segundos para o próximo "Big Bang".⊆ n n $\subseteq$ $\subseteq$ $n$$n$$n$

Pergunta 1: Que novidade uma prova (ou reprovação) de BPP = P contribuiria para o nosso conhecimento depois de conhecermos BPP P / poly? $\subseteq$

Em "novo", quero dizer consequências realmente surpreendentes, como colapso / separação de outras classes de complexidade. Compare isso com as conseqüências que a prova / reprovação de NP $\subseteq$ P / poli forneceria.

$\not\subseteq$ $[2^{O(n)}]$$2^{o(n)}$

Pergunta 2: Por que não podemos provar BPP = P de maneira semelhante à prova de BPP / poly P / poly? $\subseteq$

Um obstáculo "óbvio" é a questão do domínio finito vs. infinito: os circuitos booleanos funcionam sobre domínios finitos , enquanto as máquinas de Turing trabalham sobre o conjunto inteiro de - strings de qualquer comprimento. Portanto, para des aleatorizar os circuitos booleanos probabilísticos, basta tirar a maioria das cópias independentes de um circuito probabilístico e aplicar a desigualdade de Chernoff, juntamente com o limite da união. Obviamente, em domínios infinitos , essa regra simples de maioria não funcionará. $\{0,1\}^*$$0$$1$

Mas é este (domínio infinito) um verdadeiro "obstáculo"? Usando os resultados da teoria estatística de aprendizagem (dimensão VC), já podemos provar que BPP / poly $\subseteq$ P / poly também se aplica a circuitos que trabalham em domínios infinitos , como circuitos aritméticos (trabalhando sobre todos os números reais); veja, por exemplo, este artigo de Cucker al. Ao usar uma abordagem semelhante, tudo o que precisamos é mostrar que a dimensão VC das máquinas de Turing com tempo poli não pode ser muito grande. Alguém viu alguma tentativa de dar esse último passo?

Os resultados (conhecidos como convergência uniforme em probabilidade ) implicam o seguinte: se para cada entrada , uma função escolhida aleatoriamente (sob alguma distribuição de probabilidade em ) satisfaz para uma constante , então pode ser calculado em todas as entradas como a maioria de alguns (fixa) funciona a partir de . Veja, por exemplo, Corolário 2 no artigo de Haussler . [Para que isso ocorra, existem algumas condições leves de mensurabilidade em ] $x\in X$$\mathbf{f}\in F$$F$$\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$$c>0$$f(x)$$x\in X$$m=O(v)$$F$$F$

Por exemplo, se é o conjunto de todos os polinômios computáveis ​​por circuitos aritméticos de tamanho , todos os polinômios em têm grau no máximo . Usando limites superiores conhecidos no número de padrões zero de polinômios (veja, por exemplo, este artigo ), pode-se mostrar que a dimensão VC de é . Isso implica na inclusão BPP / poly P / poly para circuitos aritméticos.$F$$f:\mathbb{R}^n\to\mathbb{R}$$\leq s$$F$$D=2^s$$F$$O(n\log D)=O(ns)$$\subseteq$

Não tenho certeza de quanto de uma resposta é essa, apenas estou me entregando a uma reflexão.

A pergunta 1 poderia ser feita igualmente sobre P NP e com uma resposta semelhante - as técnicas / idéias usadas para provar o resultado seriam o grande avanço mais do que a própria conclusão.$\neq$

Para a Questão 2, quero compartilhar alguns antecedentes e um pensamento. Praticamente todas as técnicas e idéias que temos para BPP = P, até onde sei, passam por "derandomização": dada qualquer máquina de Turing polytime probabilística, construa um PRG para alimentá-lo com um monte de bits escolhidos deterministicamente em vez de aleatórios outros, de modo que seu comportamento seja muito semelhante ao comportamento em bits verdadeiramente aleatórios. Portanto, com geradores pseudo-aleatórios bons o suficiente, obtemos BPP = P. ("World of BPP = P" de Goldreich evidencia que qualquer prova de BPP = P deve ser igual a isso.)

Isso é muito parecido com BPP P / poli, exceto que o PRG é a sequência de conselhos que é produzida pela mágica. Talvez a melhor resposta para a sua pergunta 2 seja que, em P, não temos mágica e precisamos elaborar nós mesmos as orientações. A des randomização também é a ideia por trás do resultado de 2004 SL = L, usando ferramentas como gráficos de expansão.$\subseteq$

Agora considere o que essa prova implicaria para apenas um algoritmo em particular, o teste de primalidade de Miller-Rabin. Isso mostraria a existência de algum gerador determinístico que seleciona uma sequência de números inteiros para alimentar o teste de primalidade de Miller-Rabin, de modo que, se e somente se todos os números passassem, o número original seria primo.

Pelo que entendi (embora eu não seja especialista), a questão de saber se essa lista existe e quão pequenos podem ser os números (em particular se basta verificar todos os números abaixo de algum limite) parece uma pergunta bastante profunda em teoria dos números e está intimamente relacionada com as formas de prova da hipótese generalizada de Riemann. Veja esta pergunta . Não acho que exista uma implicação formal aqui, mas não parece algo que esperamos obter na próxima semana como um corolário miniatura acidental de uma construção PRG muito mais geral.