Mais sobre PH em PP?

Uma pergunta recente de Huck Bennett, perguntando se a classe PH estava contida na classe PP, recebeu respostas um tanto contraditórias (tudo verdade, ao que parece). Por um lado, vários resultados do oráculo foram dados ao contrário, e por outro Scott sugeriu que a resposta provavelmente é positiva, já que o teorema de Toda mostra que o PH está no BP.PP, a variante probabilística do PP, e geralmente acreditamos que a randomização não ajuda muito, por exemplo, suposições de dureza razoáveis implicam PRGs que podem substituir a randomização.

Agora, no caso do PP, não é apriori claro que mesmo um PRG "perfeito" implicará uma des randomização completa, uma vez que a derandomização natural executaria o algoritmo original com a saída do PRG para todas as sementes possíveis polinomialmente e obter a maioria dos votos . Não está claro que obter o voto da maioria entre os cálculos do PP seja algo que possa ser feito no próprio PP. No entanto, um artigo de Fortnow e Reingold mostra que o PP é fechado sob reduções da tabela da verdade (estendendo o resultado surpreendente de que o PP é fechado sob interseção), o que parece suficiente para obter essa votação majoritária.

Então, qual é a questão aqui? Toda, Fortnow-Reingold e todas as derandomizações baseadas em PRG, parecem relativizar, implicariam que a PH no PP para cada oráculo para o qual existem PRGs apropriados. Portanto, para todos os oráculos sob os quais o PP não contém PH (por exemplo, de Minski & Papert, Beigel ou Vereshchagin ), os PRGs para PP não existem. Em particular, isso implica que, para esses oráculos, não há funções apropriadamente rígidas no EXP (caso contrário, existiriam PRGs do tipo NW-IW). Olhando pelo lado positivo, isso implicaria que em algum lugar dentro de cada um desses resultados do oráculo oculte um algoritmo PP (não uniforme) para (aproximando) EXP com esse oráculo. Isso é estranho, pois todos esses resultados da Oracle parecem depender de novos limites inferiores de PP(para circuitos limiares) e são diretos em suas máquinas de construção de oráculos, portanto não vejo onde se esconde um limite superior para o PP. Talvez esse limite superior funcione de maneira geral, mostrando que a PP (não uniforme) pode calcular (ou pelo menos fornecer algum viés) toda a EXP? Algo assim não daria pelo menos uma simulação de CH de EXP?

Então, suponho que minha pergunta seja dupla: (1) essa cadeia de raciocínio faz sentido? (2) Em caso afirmativo, alguém pode "descobrir" os limites superiores implícitos para o PP?

Editar por Aaron Sterling: colidir com a página inicial e adicionar uma recompensa. Essa foi uma das minhas perguntas favoritas e ainda não tem respostas.

cc.complexity-theory counting-complexity derandomization relativization Noam
fonte

De fato, comece com uma função booleana em AC0 que não pode ser calculada por uma porta de limiar de polilog (N) graus. Para cada oráculo , definimos o idioma (onde são os bits da ésima fatia de ). Desde , , para todos . O 'th passo diagonalization vai escolher (para alguns ) tal que a ' th PP TM comete um erro em, o que acontece desde

f : {0, 1}^{N} \to {0, 1}

$f:\{0,1\}^N \rightarrow \{ 0,1\}$

A

$A$

L_{A} = {1^{n} | f (A_{n}) = 1}

$L_A= \{1^n | f(A_n)=1\}$

A_{n}

$A_n$

2^{n}

$2^n$

n

$n$

A

$A$

f \in A C 0

$f \in AC0$

L_{A} \in P H^{A}

$L_A \in PH^A$

A

$A$

t

$t$

A_{n}

$A_n$

n

$n$

t

$t$

1^{n} \in L_{A} ?

$1^n \in L_A?$

f

$f$ não é o limite do polilog (N) (como é o cálculo de uma máquina PP). Então . Mas talvez ...

L_{A} \notin P P^{A}

$L_A \not\in PP^A$

L_{A} \in P P^{A} | p o l y

$L_A \in PP^A|poly$

Noam

Portanto, para obter também , precisaríamos muitas instâncias de em um único comprimento . Isso parece facilmente factível definindo , onde para uma cadeia de bits , indica os bits que descrevem se para todos os possíveis de comprimento . Mas precisaríamos melhorar o limite inferior de para exigir que cópias de em diferentes

L_{A} \notin P P^{A} / p o l y

$L_A \not\in PP^A/poly$

f

$f$

n

$n$

L_{A} = {x | f (A_{x}) = 1}

$L_A = \{ x | f(A_x)=1\}$

n

$n$

x

$x$

A_{x}

$A_x$

2^{n}

$2^n$

x y \in A

$xy \in A$

2^{n}

$2^n$

y

$y$

n

$n$

f

$f$

N

$N$

f

$f$

N

$N$ cadeias de bits não podem ser calculadas por portas de limiar de grau polilog (N), mesmo com os bits de ajuda do polilog (N). Portanto, isso deve ser falso para qualquer . Parece um limite superior interessante.

f \in A C 0

$f \in AC0$

Noam

Pensando bem, a observação de que em todo oráculo que produz PH / ⊆ PP não existem PRGs eficientes que enganam os algoritmos BP.PP não deveria ser mais surpreendente do que o fato de que em todo oráculo que produz BPP / ⊆ P existem sem PRGs eficientes que enganam os algoritmos BPP. Isso porque todo oráculo que produz PH / ⊆ PP também produz BP.PP / ⊆ PP pelo teorema de Toda (relativizado). Mas talvez eu esteja perdendo o objetivo. -

slimton

Este é um bom ponto. No entanto, intuitivamente, quando você faz um oráculo para o qual o cerne da construção está dando um poder incomum ao , de modo que implica um poder incomum para também e, portanto, impossibilita PRGs . O oracle para não parece dar qualquer poder incomum (ou a qualquer classe), mas em vez de limitar o poder do . No entanto, não tenho certeza se essa diferença pode ser formalizada de alguma forma.

P^{A} \neq B P P^{A}

$P^A \ne BPP^A$

B P P^{A}

$BPP^A$

P^{A} / p o l y

$P^A/poly$

P H^{A} ⊈ P P^{A}

$PH^A \not\subseteq PP^A$

P^{A}

$P^A$

P P^{A}

$PP^A$

Noam

Como observei acima: nas construções para o cerne da construção está dando poder "não natural" ao BPP (e, portanto, também ao P / poly), por exemplo, plantando muitas testemunhas para o oráculo duro em lugares onde somente a randomização pode encontrá-los. Portanto, embora seja realmente interessante que esse poder seja suficiente para problemas "gerais", pelo menos o poder inesperado do P / poli é claro. Por outro lado, não vejo em nenhum lugar que o oráculo para separar o PH do PP dê poder não natural a P / poly ou a qualquer outra classe, de fato. Não tenho certeza se essa diferença é "real".

P \neq B P P

$P \ne BPP$

Noam

Mais sobre PH em PP?

Respostas: