Hierarquia para BPP vs derandomization

Em uma frase: a existência de uma hierarquia para implicaria algum resultado de des randomização?$\mathsf{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?$\mathsf{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.$\mathsf{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 $\mathsf{BPTIME}(f(n))$$f(n)$$L \in \mathsf{BPTIME}(f(n))$$T$$x \in L$$T$é 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/3$$x \not \in L$$T$$O(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 $\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$$c > 1$$\mathsf{BPTIME}$$O(\log n)$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?$\mathsf{BPTIME}(n^d) \subseteq \mathsf{DTIME}(n^c)$$d$$c$

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.$\mathsf{BPTIME}$

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:$BPP \subseteq TIME[2^{n^{c}}]$$c$$EXP \neq BPP$

• Se a PTH é falsa, então . Este é o contrapositivo do que Lance observou.$EXP \neq BPP$
• Se a PTH é verdadeiro, em seguida, "PTH implica " assim novamente E X P ≠ B P P .$BPP \subseteq TIME[2^{n^{c}}]$$EXP \neq BPP$

$EXP \neq BPP$$EXP \neq BPP$

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