Hierarquia para BPP vs derandomization

29

Em uma frase: a existência de uma hierarquia para implicaria algum resultado de des randomização?BPTIME

Uma questão relacionada, mas mais vaga, é: a existência de uma hierarquia para implica limites inferiores difíceis? A resolução desse problema atinge uma barreira conhecida na teoria da complexidade?BPTIME

Minha motivação para esta questão é entender a dificuldade relativa (em relação a outros grandes problemas em aberto na teoria da complexidade) de mostrar uma hierarquia para . Suponho que todos acreditem que essa hierarquia exista, mas, por favor, corrija-me se pensar de outra forma.BPTIME

Alguns antecedentes : contém os idiomas cuja associação pode ser decidida por uma máquina de tornear probabilística no tempo f ( n ) com probabilidade limitada de erro. Mais precisamente, uma linguagem L B P T I M E ( f ( n ) ) se existe uma máquina de Turing probabilística T tal que, para qualquer x L a máquina TBPTIME(f(n))f(n)LBPTIME(f(n))TxLTé executado em tempo e aceita com probabilidade de, pelo menos, 2 / 3 , e para qualquer x L , T é executado em tempo O ( f ( | x | ) ) e rejeita com probabilidade de pelo menos 2 / 3 .O(f(|x|))2/3xLTO(f(|x|))2/3

Incondicionalmente, está aberta se para todos c > 1 . Barak mostrou que existe uma hierarquia estrita para B P T I M E para máquinas com O ( log n )BPTIME(nc)BPTIME(n)c>1BPTIMEO(logn)conselho. Fortnow e Santhanam aprimoraram isso para 1 conselho. Isso me leva a pensar que provar a existência de uma hierarquia probabilística do tempo não está muito longe. Por outro lado, o resultado ainda está aberto e não consigo encontrar nenhum progresso após 2004. As referências, como sempre, podem ser encontradas no zoológico .

A relação com a des aleatorização vem dos resultados de Impagliazzo e Wigderson: eles mostraram que, sob uma hipótese plausível de complexidade, para qualquer constante d e alguma constante c . Pelos teoremas clássicos da hierarquia de tempo para o tempo determinístico, isso implica uma hierarquia de tempo para o tempo probabilístico. Estou fazendo a pergunta inversa: uma pesquisa probabilística atinge uma barreira relacionada à prova de resultados de des aleatorização?BPTIME(nd)DTIME(nc)dc


EDIT: Estou aceitando a resposta de Ryan como uma solução mais completa.

Se alguém tiver observações sobre o que está entre nós e provar a existência de uma hierarquia por tempo probabilístico, fique à vontade para responder / comentar. Obviamente, a resposta óbvia é que tem uma definição semântica que desafia as técnicas clássicas. Estou interessado em observações menos óbvias.BPTIME

Sasho Nikolov
fonte

Respostas:

22

Seja PTH a hipótese de que exista uma hierarquia probabilística de tempo. Suponha que a resposta à sua pergunta seja verdadeira, ou seja, "PTH implica " para alguns pontos c . Então, E X P B P P seria incondicionalmente verdadeiro. Considere dois casos:BPPTIME[2nc]cEXPBPP

  • Se a PTH é falsa, então . Este é o contrapositivo do que Lance observou.EXPBPP
  • Se a PTH é verdadeiro, em seguida, "PTH implica " assim novamente E X P B P P .BPPTIME[2nc]EXPBPP

EXPBPPEXPBPP

Ryan Williams
fonte
3
Agradável. Portanto, existe uma forte barreira contra a demonstração de que existe uma barreira relacionada à des randomização para provar o PTH.
Sasho Nikolov 27/05
18

Não é difícil derivar uma hierarquia probabilística de tempo se BPP = EXP, o caso extremo de não des aleatorização.

Lance Fortnow
fonte
2
E você não precisa de BPP = EXP, só precisa de BPP não em DTIME (2 ^ {n ^ c)}) para uma constante c> 1. Ou seja, você só precisa que o BPP seja difícil para o DTIME, não que o BPP pode resolver idiomas E-complete. Isso diz que a extrema falta de des aleatorização implica uma hierarquia. E a falta intermediária de des aleatorização?
Jeff Kinne
Boas observações. Portanto, um colapso é tão bom quanto um colapso para estabelecer uma hierarquia. Isso mina minha motivação, mas, tecnicamente falando, ainda não é possível que uma hierarquia probabilística implique des randomização, mesmo que a falta de des randomização implique uma hierarquia probabilística (uma afirmação falsa pode implicar uma afirmação verdadeira)? A pergunta mais vaga sobre quais barreiras o problema da hierarquia do BPP atinge ainda permanece. Por exemplo, é possível que o BPP tenha uma hierarquia para todos os oráculos (a questão não resolvida de Fortnow-Sipser'89), para que a relativização não seja um problema em aberto.
Sasho Nikolov 27/05