Qual é o oráculo de complexidade mínima que separa o PSPACE da hierarquia polinomial?

fundo

Sabe-se que existe um oráculo $A$ tal que, $PSPACE^A \neq PH^A$ .

É sabido até que a separação se aplica a um oráculo aleatório. Informalmente, pode-se interpretar isto para dizer que há muitas oráculos para os quais $PSPACE$ e $PH$ são separados.

Questão

Como complicado são estes oráculos que separam $PSPACE$ a partir de $PH$ . Em particular, existe um oráculo $A \in DTIME(2^{2^{n}})$ tal que $PSPACE^A \neq PH^A$ ?

Temos algum oráculo $A$ tal que $PSPACE^A \neq PH^A$ e $A$ tenham um limite superior de complexidade conhecido?

Nota: a existência de tal oráculo pode ter ramificações na teoria da complexidade estrutural. Consulte a seguinte atualização abaixo para obter mais detalhes.

Atualizar com detalhes sobre uma técnica de limite inferior

Reivindicação: Se , então para todos os oráculos Um ∈ P / p o l y , P S P A C E A = P H A .$PSPACE = PH$$A \in P/poly$$PSPACE^A = PH^A$

Esboço prova: Suponha-se que .$PSPACE = PH$

Seja dado um oráculo . Podemos construir uma máquina de Turing M de oráculo de tempo polinomial Σ 2 que, para um determinado comprimento n , adivinha um circuito de tamanho p ( n ) usando uma quantificação existencial e verifica se o circuito decide A comparando a avaliação do circuito e o resultado da consulta para cada comprimento n string usando uma quantificação universal.$A \in P/poly$$\Sigma_2$$M$$n$$p(n)$$A$$n$

Além disso, considere um problema de decisão ao qual estou me referindo como circuito booleano quantificado (QBC), no qual você recebe um circuito booleano quantificado e deseja saber se ele é válido (semelhante ao QBF). Esse problema está completo no PSPACE porque o QBF está completo no PSPACE.

Por hipótese, segue-se que QBC . Digamos Q B C ∈ Σ k para alguns k suficientemente grandes. Let N denotar um tempo polinomial Σ k máquina de Turing que resolve QBC.$\in PH$$QBC \in \Sigma_k$$k$$N$$\Sigma_k$

Podemos misturam o cálculo de e N (semelhante ao que é feito na prova do teorema Karp-Lipton) para obter um tempo polinomial Σ k máquina do Oracle Turing que resolve Q B C A .$M$$N$$\Sigma_k$$QBC^A$

Informalmente, essa nova máquina recebe como entrada um QBC da Oracle (ou seja, um QBC com portas da Oracle). Em seguida, calcula um circuito que calcula nas entradas de comprimento n (disparando simultaneamente os dois primeiros quantificadores). Em seguida, ele substitui os portões Oracle no QBC oráculo com o circuito para um . Finalmente, procede-se a aplicar o restante do tempo polinomial Σ k algoritmo para resolver Q B C neste exemplo modificado.$A$$n$$A$$\Sigma_k$$QBC$

Agora, podemos mostrar o limite inferior condicional.

Corolário: Se existe um oráculo tal que P S P A C E UM ≠ P H A , em seguida, N E X P ⊈ P / p o l y .$A \in NEXP$$PSPACE^A \neq PH^A$$NEXP \nsubseteq P/poly$

Esboço prova: Suponha-se que existe tal que P S P A C E UM ≠ P H Uma . Se N E X P ⊆ P / p o l y , teríamos uma contradição.$A \in NEXP$$PSPACE^A \neq PH^A$$NEXP \subseteq P/poly$

Em particular, se , em seguida, pela reivindicação acima temos P S P A C E ≠ P H . No entanto, sabe-se que N E X P ⊆ P / p o l y implica que P S P A C E = P H .$NEXP \subseteq P/poly$$PSPACE \neq PH$$NEXP \subseteq P/poly$$PSPACE = PH$

(veja aqui alguns detalhes sobre resultados conhecidos para P / poli)

Acredito que se você seguir o argumento apresentado, por exemplo, na Seção 4.1 da pesquisa de Ker-I Ko , obterá um limite superior de . De fato, podemos substituir n 2 aqui por qualquer função n f ( n ) onde f ( n ) → ∞ como n → ∞ . Não foi exatamente o que foi solicitado, mas está próximo.$\mathsf{DTIME}(2^{2^{O(n^2)}})$$n^2$$nf(n)$$f(n) \to \infty$$n \to \infty$

Em particular, usando a conversão entre separações de oráculos e limites inferiores do circuito, e seguindo a notação de Ko, temos o seguinte:

• Iremos diagonalizar sobre cadeias de comprimento que p n ( x ) = x n + n é "o" n- ésimo polinômio (em alguma enumeração de algoritmos de politempo) e m ( n ) será especificado abaixo.$t(n) = p_n(m(n))$$p_n(x) = x^n + n$$n$$m(n)$

• Traduzindo para limites inferiores do circuito, isso significa que estamos considerando circuitos de profundidade limitada em entradas de .$2^{t(n)}$

• O requisito (ver p. 15 de Ko) precisamos de para satisfazer $m(n)$para todos osn. Aquidé a profundidade dos circuitos com os quais queremos diagonalizar, ou equivalente, o nívelΣ p d dePH com oqual queremos diagonalizar. Para diagonalizar contra todosPH, simplesmente escolherdpara ser uma função den, que éω(1); podemos escolher um$\frac{1}{10} 2^{m/(d-1)} > d p_n(m(n))$$n$$d$$\mathsf{\Sigma_d^p}$$\mathsf{PH}$$\mathsf{PH}$$d$$n$$\omega(1)$$d$isso cresce arbitrariamente lentamente (talvez sujeito a alguma suposição de computabilidade em , mas isso não deve ser obstáculo). Se adivinhamos que d ( n ) é constante (mesmo que não seja, mas crescerá arbitrariamente lentamente), vemos que m ( n ) em torno de 2 n deve funcionar.$d(n)$$d(n)$$m(n)$$2^n$

• Isso significa que , então estamos procurando um limite inferior contra circuitos com entradas ∼ 2 2 n 2 .$t(n) \sim 2^{n^2}$$\sim 2^{2^{n^2}}$

• Trevisan e Xue (CCC '13) mostraram que se pode encontrar um compromisso no qual um circuito de profundidade limitada dado em entradas não paridade de computação com uma semente de p o l y L o g ( N ) de comprimento.$N$$polylog(N)$

• For us $N=2^{2^{n^2}}$, so $polylog(N) = 2^{O(n^2)}$. We can brute force over such seeds in $2^{2^{O(n^2)}}$ time and use the first one that works.

To replace the $n^2$ with $nf(n)$, just let $p_n(x) = x^{f(n)} + f(n)$ instead.

Interestingly, if I'm understanding correctly, I believe this implies that if one could improve the Trevisan-Xue...

• ...to a pseudodeterministic/Bellagio algorithm (see Andrew Morgan's comment below), one would get that $\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$; or

• ... com um algoritmo não-determinístico que supôs os bits, mas, em seguida, correu em p o l y ( n ) de tempo, e de tal modo que em qualquer caminho aceitando-a faz com que a mesma saída ( cf. N P S V ), implicaria N E X P ⊈ P / p $polylog(N)$$poly(N)$$\mathsf{NPSV}$$\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$

• ... para um algoritmo determinístico, obteríamos $\mathsf{EXP} \not\subseteq \mathsf{P/poly}$

Por um lado, isso sugere por que a des randomização do lema da troca ainda deve ser difícil - um argumento que não tenho certeza de que era conhecido antes! Por outro lado, isso me parece um tipo interessante de dureza versus aleatoriedade (ou isso é realmente uma coisa nova, oráculos versus aleatoriedade?).