Qual é a simulação mais rápida conhecida do BPP usando os algoritmos de Las Vegas?

$\mathsf{BPP}$ e $\mathsf{ZPP}$ são duas classes de complexidade probabilística básica.

$\mathsf{BPP}$ é a classe de linguagens decidida pelos algoritmos de Turing probabilísticos em tempo polinomial, nos quais a probabilidade do algoritmo retornar uma resposta incorreta é limitada, ou seja, a probabilidade de erro é no máximo $\frac{1}{3}$ (para instâncias SIM e NÃO).

Por outro lado, $\mathsf{ZPP}$ algoritmos podem ser vistos como esses algoritmos probabilística que nunca mais voltar uma resposta errada, sempre que retornar uma resposta que está correcto. No entanto, seu tempo de execução não é limitado por um polinômio, eles são executados no polinômio esperado.

Seja $\mathsf{ZPTime}(f)$ a classe da linguagem decidida por algoritmos probabilísticos com probabilidade de erro zero e tempo de execução esperado $f$ . Estes também são referidos como algoritmos de Las Vegas e $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Minha pergunta é o que é melhor saber simulação de algoritmos $\mathsf{BPP}$ usando algoritmos de Las Vegas? Podemos simulá-los no tempo esperado subexponencial? Existe alguma melhoria conhecida sobre a simulação trivial de força bruta que leva tempo exponencial?

Mais formalmente, sabemos se ou $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ para alguns? $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ $\epsilon>0$

cc.complexity-theory complexity-classes randomness randomized-algorithms echuly
fonte

Qual é n, o comprimento da entrada? Por que podemos aceitar em

2^{n}

$2^n$

27613 domotorp

é a mesma coisa que

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

Emil Jerabek

Acho a pergunta bastante interessante. Editei a pergunta para torná-la mais legível e precisa. Sinta-se livre para editar mais. ps: eu estou supondo que você provavelmente quis levar em conta as polinomialmente muitos bits aleatórios usados pelo algoritmo BPP como parâmetro para o tempo de simulação, mas como Emil aponta o que você escreveu dá

. Se você deseja substituir o BPP por uma classe específica de algoritmos probabilísticos de erro limitado que possuem um parâmetro para o número de bits aleatórios usados pelo algoritmo.

2^{p o l y (n)}

$2^{poly(n)}$

precisa

Você pode perguntar se podemos simular um algoritmo BPP que use

bits aleatórios em

pois a simulação de força bruta é executada em

tempo.

r (n)

$r(n)$

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$

Kaveh

Respostas:

Primeiro, observe que se para alguma constante , então $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ . (Prova da hierarquia de tempo não determinística.) Portanto, provar tal inclusão seria significativo, não apenas porque é uma simulação aprimorada, mas também produziria o primeiro progresso nos limites inferiores do tempo aleatório em décadas. $\mathsf{BPP} \neq \mathsf{NEXP}$

Em seguida, considere a classe $\mathsf{PromiseBPP}$ , para os quais o seguinte problema é " -Hard": $\mathsf{PromiseBPP}$

Problema de probabilidade de aproximação de circuito (CAPP): dado um circuito , emita a probabilidade de aceitação de dentro de $C$ $C$ factor de aditivo. $1/6$

Resultados de Impagliazzo, Kabanets, e Wigderson 2.002 implica que um algoritmo de erro de tempo zero para CAPP (onde é o tamanho de ) implicaria . No STOC'10, estendi isso para mostrar: supondo que para cada com bits de entrada e tamanho , é possível calcular o CAPP de forma não determinística (portanto, o erro zero é suficiente) em $2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ tempo, então . Ou seja, certamente existem problemas computáveis com a aleatoriedade dos erros nos dois lados, para a qual algoritmos de erro zero que mesmo vencem levemente a pesquisa exaustiva implicariam limites inferiores do circuito. Eu acredito que isso deve ser interpretado como um método possível para provar limites mais baixos; sua milhagem pode variar. $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$

Note-se que mesmo provando também está aberta, e provando que implicaria também limites inferiores: por Kabanets e Impagliazzo 2004, se o teste de identidade polinomial (um problema) é em para todos , temos limites inferiores para Permanente ou $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\varepsilon > 0$ $\mathsf{NEXP}$ . Recentemente (próximos em STOC'13), que provou ser incondicionalmente que quer ou tem circuitos de tamanho, baseando-se no método de "testemunha fácil" de Kabanets. Isso implica duas coisas: $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ $\mathsf{RTIME}[2^n]$ $n^c$

Há um de tal modo que para todos , é incondicionalmente em - esta é a melhor sobre derandomization incondicional de em $c$ $\varepsilon > 0$ $\mathsf{RP}$ $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ $\mathsf{RP/BPP}$ que sabemos até agora. $\mathsf{ZPP}$
Para começar a receber simulações subexponencial interessantes do , você "apenas" tem que assumir não tem circuitos de polinômio de tamanho fixo. $\mathsf{BPP}$ $\mathsf{RTIME}[2^n]$

Ryan Williams
fonte

Graças à Niel para tomar o tempo para fazer a minha resposta legível :)

Ryan Williams

Ryan, acho que estou prestes a fazer uma pergunta muito estúpida, mas aqui vou eu: em sua primeira frase, por que você precisa "para todos

"? O subconjunto BPP de ZPTIME (2 ^ (n ^ c)) para alguns c fixos implica o subconjunto BPP de RTIME (2 ^ (n ^ c)) e, portanto, NTIME (2 ^ (n ^ c)), portanto, o BPP é diferente de NEXP ou de outra forma NTIME (2 ^ (2n ^ c)) é um subconjunto de NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Sasho Nikolov 01/04

Nada estúpido - de fato,

para alguns

é suficiente para

, obrigado por apontar isso. Algoritmos de tempo subexponenciais são necessários para as outras conseqüências.

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

Ryan Williams

Ryan: Se eu quisesse entender o seu trabalho, com que livro (s) sobre complexidade de circuitos você recomenda estar familiarizado?

T ....

Oi Arul, felizmente Bill Gasarch me fez esta pergunta um tempo atrás, e colocar-se a seguinte página de links: cs.umd.edu/~gasarch/ryan/ryan.html

Ryan Williams

Depende de quais suposições você está disposto a fazer.

Sob certas premissas de dureza, nomeadamente , obtém que . Isto implica, em particular, que e, portanto, que todas as línguas $E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$ sejam aceitos por uma máquina de Las Vegas (consulte "P = BPP, a menos que E possua circuitos subexponenciais: derandomizando o lema XOR", de Impagliazzo e Wigderson).

Também é possível fazer uma suposição dureza mais leves, ou seja, que , e conseguir que (ver Lema 46 em "Na procura de um testemunha fácil: tempo exponencial versus tempo polinomial probabilístico "de Impagliazzo, Kabanets e Wigderson). $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

Ou Meir
fonte

Exceto quaisquer avanços na des aleatorização, parece-me que o requisito de que a Las Vegas Machine não cometa erros é crucial, de modo que há pouco ou nenhum benefício em ter aleatoriedade neste caso.

Para uma BPP linguagem decidido por um algoritmo adequado , que atua nas entradas e uma seqüência aleatória representando suas escolhas aleatórias, o critério de erros zero implica que a máquina de Las Vegas deve verificar com certeza qual dos dois casos $L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$ detém. Se não é dada nenhuma informação sobre os, então este é essencialmente um problema promessa Oracle: dado um oráculocomputação, e dado a promessa de querendimentos de uma saída depara pelo menos duas vezes mais entradas que a saída oposta, determine qual saída é mais comum.

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$

A^{'}

$A'$

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Embora a Las Vegas Machine possa usar técnicas aleatórias, se formos forçados a tratar como um oráculo, podemos ver que a única estratégia disponível para uma máquina de Las Vegas é fazer uma pesquisa relativamente completa (embora não exaustiva) do seqüências aleatórias , para ver qual resposta é dada para cada uma. Só pode ter certeza se encontra mais de $A'$ $r$ cordas distintas que dão origem à mesma saída; caso contrário, com probabilidade pequena (mas diferente de zero!), pode ser azarado e obter uma amostra não representativa das saídas possíveis. Para obter erro zero, ele deve amostrar pelo menos $2^{N(n)}\!/3$ $r$ entradas . $2^{N(n)}\!/3$ $r$

Como a máquina de Las Vegas deve inspecionar pelo menos uma fração constante de todas as seqüências aleatórias possíveis , assintoticamente não estamos em melhor situação do que se testássemos deterministicamente todas as sequências aleatórias possíveis. Não obtemos vantagem assintótica na simulação aleatória de algoritmos de BPP em um ambiente de erro zero, além do que podemos fazer deterministicamente por força bruta. $r$

Observe que esse mesmo argumento dá origem a uma separação do oráculo entre BPP e ZPP , ou seja , existe um oráculo tal que porque o algoritmo ZPP leva tempo exponencial, enquanto um algoritmo BPP pode resolver a questão sobre o oracle em uma única consulta e tenha sucesso com erro limitado. No entanto, isso não diz mais do que você já suspeitava (que a sobrecarga da simulação pode ser pior que o polinômio) nem que os assintóticos são tão ruins quanto uma simulação determinística ingênua. $A$

{Z P P}^{A} ⫋ {B P P}^{A}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Niel de Beaudrap
fonte

corrija-me se estiver errado: você está apresentando um raciocínio intuitivo sobre o porquê da des randomização parecer impossível, mas sabemos que, sob algumas suposições razoáveis, BPP, ZPP e P são a mesma coisa. de modo que a intuição não é necessariamente bom

Sasho Nikolov

De modo nenhum. A des randomização seria presumivelmente um insight de como simular BPP por P , não é? Estou apenas descrevendo como, se ele deseja resultados incondicionais que não exploram a estrutura do próprio algoritmo, ele pode também executar uma simulação determinística como uma aleatória com erro zero. Ou há algo errado com esta explicação?

Niel de Beaudrap 28/03

Acho que tudo o que você está dizendo é que a simulação de força bruta ingênua do BPP por ZPP não é muito mais rápida que a simulação de força bruta ingênua de BPP por P., mas não consigo ver o que isso deve mostrar. para mim, isso é como alguém perguntando 'qual é o algoritmo mais rápido para encontrar uma correspondência máxima' e obtendo como resposta 'bem, falhando em ter uma ideia da estrutura das correspondências, é tempo exponencial'. a questão está pedindo se há alguma introspecção conhecido na estrutura do BPP que faz simulação ZPP eficiente possível

Sasho Nikolov

@ShohoNikolov: Na verdade, não era para ser um insight profundo. Pela redação da pergunta, pareceu-me limítrofe a migração para o CS.SE. Decidi respondê-lo literalmente, a saber: até onde sabemos , o tempo de execução esperado mais eficiente da Las Vegas Machine que aceita uma linguagem L∈BPP não é muito melhor do que uma máquina determinística que explora as possibilidades de força bruta. Respostas que dizem que pode ser um limite superior polinomial se algumas condições forem excelentes e informativas, e eu voto a favor; mas eu dirijo a questão real.

Niel de Beaudrap 28/03

Eu acho que essa é uma boa resposta (também mais legível agora após a edição). Não temos um resultado condicional como "P = ZPP implica P = BPP" ou "ZPP = BPP implica P = BPP", portanto ainda é possível simular algoritmos BPP por ZP mais rapidamente do que com algoritmos determinísticos. No entanto, o resultado da relativização parece implicar que isso não pode acontecer com nenhuma simulação de relativização, entendi corretamente?

Kaveh