conseqüências

Sabemos que são equivalentes e a hierarquia polinomial cai para o nível.

Quais são os outros colapsos e consequências não triviais?

$\newcommand{\co}{\mathsf{co}\text{-}}$ $\newcommand{\class}[1]{\mathsf{#1}}$

Se , você terá um colapso no primeiro nível, a saber .$\class{PP}=\class{RP}$$\class{PH}=\class{NP}$

Suponha , uma vez que está fechado sob complemento, temos , portanto .$\class{PP}=\class{RP}$$\class{PP}$$\mathsf{RP}=\co{\class{RP}}=\class{ZPP}$$\class{PP}=\class{ZPP}$

Usando o teorema de Toda:

$\class{PH}\subseteq\class{P^{\class{PP}}}=\class{P}^{\class{ZPP}}=\class{ZPP}\subseteq{\class{NP}}$ .

Você realmente obtém algo mais forte, se , a hierarquia entra em colapso para .$\class{PP}=\class{RP}$$\class{ZPP}$

De fato, você pode mostrar que a hierarquia de contagem cai para , usando argumentos mais simples que o teorema de Toda, e obter .$\class{ZPP}$$\class{PH}\subseteq\class{CH}\subseteq\class{ZPP}$

Um argumento tentador seria dizer que, uma vez que e são baixos por si só, ou seja, então e recolhidos em . Isso é obviamente falso, uma vez que onde são conjuntos de idiomas "decidíveis" por tipos específicos de máquinas de Turing (tipos e ), não implica para qualquer oracle . Vejo$\class{PP}=\class{ZPP}$$\class{ZPP}$$\class{ZPP}^{\class{ZPP}}=\class{ZPP}$$\class{PP}^{\class{PP}}=\class{ZPP}^{\class{ZPP}}=\class{ZPP}$$\class{CH}$$\class{ZPP}$$\class{A}=\class{B}$$\class{A},\class{B}$$\class{A}$$\class{B}$$\class{A}^{\mathcal{O}}=\class{B}^{\mathcal{O}}$$\mathcal{O}$esta resposta para mais explicações.

O que você realmente precisa mostrar, para obter (é claro, sob a suposição original de , é essa é baixo para , ou seja, . Se isso ocorrer, então e, portanto, . Felizmente, isso não é muito difícil (e pode até ser fortalecido para é baixo para ).$\class{CH}\subseteq{ZPP}$$\class{PP}=\class{RP})$$\class{ZPP}$$\class{PP}$$\class{PP}^{\class{ZPP}}=\class{PP}$$\class{PP}^{\class{PP}}=\class{PP}^{\class{ZPP}}=\class{PP}=\class{ZPP}$$\class{CH}\subseteq\class{ZPP}$$\class{BPP}$$\class{PP}$

Se for um idioma em , existe uma máquina de Turing de tempo polinomial probabilístico com acesso a um oracle , chame-o de , de modo que:$L$$\class{PP}^{\class{ZPP}}$$\class{ZPP}$$\mathcal{O}$$M_{\mathcal{O}}$

$x\in L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]>\frac{1}{2}$ e

$x\notin L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]\le\frac{1}{2}-\frac{1}{2^{n^c}}$ .

Onde é o tempo de execução de (na definição padrão, a segunda desigualdade aparece com , no entanto, pode ser melhorada para e, portanto, ao acima).$n^c$$M_{\mathcal{O}}$$\le\frac{1}{2}$$<\frac{1}{2}$

Suponha que a máquina de Turing que decide tenha esperado o tempo de execução . Agora, vejamos a máquina , que substitui cada chamada oracle de por uma simulação em etapas da máquina para e repete essa simulação vezes . Se nos deparamos com uma chamada de oráculo, para o qual este processo não resultou em uma resposta (nenhum dos -passos simulações interrompido), então rejeita.$\mathcal{O}$$n^d$$M$$M_{\mathcal{O}}$$t$$\class{ZPP}$$\mathcal{O}$$k$$k$ $t$$M$

Deixe denotar o evento em que todas as simulações foram interrompidas no tempo determinado:$H$

$\Pr\left[\text{M accepts x}\right]=\Pr\left[\text{M accepts x} | H\right]\Pr[H]+\Pr\left[\text{M accepts x}\Big| \overline{H}\right]\Pr\left[\overline{H}\right]=\Pr\left[\text{M accepts x} | H\right]\Pr[H]=\Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]\Pr[H]$ .

Assim, temos:

$x\in L\Rightarrow \Pr\left[\text{M accepts x}\right]>\frac{1}{2}\Pr[H]$ e

$x\notin L\Rightarrow \Pr\left[\text{M accepts x}\right]\le\left(\frac{1}{2}-\frac{1}{2^{n^c}}\right)\Pr[H]\le \frac{1}{2}-\frac{1}{2^{n^c}}$ .

Pela desigualdade de Markov, uma única simulação não para com probabilidade , de modo que as simulações steps não produzem uma resposta com probabilidade . Pelo limite da união, temos , para e . Nesse caso, obtém a seguinte separação:$\le \frac{n^d}{t}$$k$ $t$$\le \left(\frac{n^{d}}{t}\right)^k$$\Pr[H]\ge 1-n^c\left(\frac{n^{d}}{t}\right)^k\ge 1-\frac{1}{2^{n^c}}$$t=2n^d$$k=2n^c$$M$

$x\in L\Rightarrow \Pr\left[\text{M accepts x}\right]>\frac{1}{2}\left(1-2^{-n^c}\right)$ e

$x\notin L\Rightarrow \Pr\left[\text{M accepts x}\right]\le \frac{1}{2}-2^{-n^c}<\frac{1}{2}-\frac{1}{2}2^{-n^c}$

O que prova , pois podemos substituir a constante por qualquer função . Veja esta pergunta para provar por que podemos substituir por qualquer constante racional e convencer-se de que ela se generaliza imediatamente para qualquer .$L\in \class{PP}$$\frac{1}{2}$$f(x)\in \class{FP}$$\frac{1}{2}$$f\in \class{FP}$