Classes de complexidade P / Poly vs Uniform

Não se sabe se NEXP está contido em P / poli. De fato, provar que o NEXP não está em P / poli teria algumas aplicações na des aleatorização.

1. Qual é a menor classe uniforme C para a qual se pode provar que C não está contido em P / poli?

2. Mostrar que o co-NEXP não está contido em P / poli teria outras consequências teóricas da complexidade, como no caso NEXP vs P / poli?

Nota: Estou ciente de que é conhecido por não estar contido no para cada constante fixa (isso também foi mostrado para MA com 1 bit de aviso). Mas nesta pergunta não estou interessado em resultados para k fixo . Estou realmente interessado em aulas diferentes de P / Poly, mesmo que sejam muito grandes.$SP_2$$Size[n^k]$$k$$k$

$\let\mr\mathrm$ Existem vários resultados na literatura que afirmam que uma determinada classe satisfaz para qualquer , e geralmente é simples preenchê-los para mostrar que a versão superpolinomialmente expandida de não está em .$C$$C\nsubseteq\mr{SIZE}(n^k)$$k$$C$$\mr{P/poly}$

Deixe-me dizer que é um limite superpolinomial se for construtível pelo tempo . Por exemplo, é um limite superpolinomial. De fato, um exercício instrutivo mostra que se é uma função computável monótona e ilimitada, existe um limite superpolinomial tal que . f ( n ) = N ω ( 1 ) n log log log log n g ( n ) f f ( n ) ≤ n g ( n $f\colon\mathbb N\to\mathbb N$$f(n)=n^{\omega(1)}$$n^{\log\log\log\log n}$$g(n)$$f$$f(n)\le n^{g(n)}$

Primeiro, a diagonalização direta mostra que para qualquer . O mesmo argumento fornece:$\Sigma_4^P\nsubseteq\mr{SIZE}(n^k)$$k$

• Se for qualquer limite superpolinomial, então .$f$$\Sigma_4\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Esboço de prova: para qualquer , seja o primeiro circuito lexicograficamente de tamanho que calcula uma função booleana em variáveis ​​não computáveis ​​por um circuito de tamanho . Então, o idioma definido por funciona.C n 2 f ( n ) n < f ( n ) L x ∈ $n$$C_n$$2f(n)$$n$$<f(n)$$L$$x\in L\iff C_{|x|}(x)=1$

Uma melhoria conhecida afirma que para qualquer . Da mesma forma,$S_2\mr P\nsubseteq\mr{SIZE}(n^k)$$k$

• Se for qualquer limite superpolinomial, então .S 2 - T I M E ( f ( n ) ) ⊈ P / p o l $f$$S_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Esboço prova: Se não, então, em particular, , portanto, . Por um argumento de preenchimento, , não .P H = S 2 P Σ 4 - t I M E ( f ( n ) ) ⊆ S 2 - t I M E ( f ( n ) ) ⊆ P / p o l $\mr{NP}\subseteq S_2\mr P\subseteq\mr{P/poly}$$\mr{PH}=S_2\mr P$$\Sigma_4\text-\mr{TIME}(f(n))\subseteq S_2\text-\mr{TIME}(f(n))\subseteq\mr{P/poly}$

Classes inconscientes se saem ainda melhor. Levando em conta a objeção levantada por Apoorva Bhagwat, vamos . Então para qualquer , e o mesmo argumento gera:N L i n ∪ O 2 P ⊈ S I Z E ( n k ) $\mr{NLin=NTIME}(n)$$\mr{NLin}\cup O_2\mr P\nsubseteq\mr{SIZE}(n^k)$$k$

• Se for qualquer limite superpolinomial, então .N L i n ∪ O 2 - T I M E ( f ( n ) ) ⊈ P / p o l $f$$\mr{NLin}\cup O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Esboço prova: Se , seguida por preenchimento, , o que implica . Então procedemos como antes.N P ⊆ P / p o l y P H = S 2 $\mr{NLin\subseteq P/poly}$$\mr{NP\subseteq P/poly}$$\mr{PH}=O_2\mr P$

Também existem resultados envolvendo MA. O resultado frequentemente mencionado de que é um exagero. Santhanam provou para qualquer , e um argumento semelhante fornece:p r o m i s de e - H Uma ∩ p r o m i s de e - c O H Uma ⊈ S I Z E ( n k ) $\mr{MA\text-EXP\nsubseteq P/poly}$

$$\mr{promise\text-MA\cap promise\text-coMA\nsubseteq SIZE}(n^k)$$ $k$

• Se for qualquer limite superpolinomial, então p r o m i s de e - H A - T I M E ( f ( n ) ) ∩ p r o m i s de e - c o M Um - t I M E ( f ( n ) ) ⊈ P / p o l y$f$

  $$\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}.$$

  Esboço de prova: pelo Lemma 11 de Santhanam (que é uma versão aprimorada do fato padrão de que com um provador PSPACE), há uma linguagem completa do PSPACE e um oracle TM-oracle aleatório TM tal que na entrada , apenas solicita consultas oracle de comprimento; se , então aceita com probabilidade ; e se , então para qualquer oráculo , aceita com probabilidade . L M x M | x | x ∈ G M G ( x ) 1 x ∉ G A M A ( x ) ≤ 1 /$\mr{PSPACE=IP}$$L$$M$$x$$M$$|x|$$x\in L$$M^L(x)$$1$$x\notin L$$A$$M^A(x)$$\le1/2$

  Para um polinômio monótono adequado , seja o problema de promessa definido por Seja uma redução polinomial de em seu complemento e seja o problema da promessa A = ( A Y E S , A N O ) ( x , s ) ∈ A Y E $p$$A=(A_{\mr{YES}},A_{\mr{NO}})$

  $$\begin{align} (x,s)\in A_{\mr{YES}}&\iff\exists\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\land\Pr[M^C(x)\text{ accepts}]=1\bigr),\\ (x,s)\in A_{\rlap{\mr{NO}}\phantom{YES}}&\iff\forall\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\to\Pr[M^C(x)\text{ accepts}]\le1/2\bigr). \end{align}$$ L B = ( B Y E S , B N O ) ( x , s ) ∈ B Y $h(x)$$L$$B=(B_{\mr{YES}},B_{\mr{NO}})$ $$\begin{align} (x,s)\in B_{\mr{YES}}&\iff(x,s)\in A_{\mr{YES}}\land(h(x),s)\in A_{\mr{NO}},\\ (x,s)\in B_{\rlap{\mr{NO}}\phantom{YES}}&\iff(x,s)\in A_{\mr{NO}}\land(h(x),s)\in A_{\mr{YES}}. \end{align}$$ Se for escolhido adequadamente grande, Portanto, suponhamos por contradição que tenha circuitos de tamanho polinomial, digamos, . Vamos denotar o tamanho do menor circuito de computação nas entradas de comprimento e colocar ; mais precisamente, EntãoB ∈ p r o m i s de e - H A - T I M E ( f ( n ) ) ∩ k ) s ( n ) L n T ( n ) = f - 1 ( p ( s ( n ) ) ) t ( $p(n)$B B ∈ S I Z E ( $$B\in\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n)).$$ $B$$B\in\mr{SIZE}(n^k)$$s(n)$$L$$n$$t(n)=f^{-1}(p(s(n)))$x ↦ ( x , 1 t ( n ) $$t(n)=\min\{m:p(s(n))\le f(m)\}.$$ $x\mapsto(x,1^{t(n)})$ é uma redução de para , portanto , o que significa Mas como é superpolinomial, temos . Isso dá uma contradição para suficientemente grande.B L ∈ S I Z E ( t ( n ) k ) s ( $L$$B$$L\in\mr{SIZE}(t(n)^k)$f t ( n ) = s ( n ) O ( 1 ) $$s(n)\le t(n)^k.$$ $f$$t(n)=s(n)^{o(1)}$$n$

Se preferirmos um resultado com uma versão não promissora do MA, Miltersen, Vinodchandran e Watanabe, provaram que para uma função semi-exponencial . Podemos lo de duas maneiras: primeiro, ele vale para - limites exponenciais para qualquer constante , e segundo, para classes alheias. Aqui, uma função -exponential é, grosso modo, uma função tal que sustenta

$$\mr{MA\text-TIME}(f(n))\cap\mr{coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}$$ $f$$\tfrac1k$$k$$\tfrac1k$$f$$\underbrace{f\circ\dots\circ f}_k=\exp$. Veja o artigo de Miltersen – Vinodchandran – Watanabe e suas referências para a definição precisa; envolve uma família bem comportada de funções bem comportadas , , de modo que , e . Além disso, se e , em seguida, . Então nós temos:$e_\alpha(x)$$\alpha\in\mathbb R_+$$e_0(x)=x$$e_1(x)=e^x-1$$e_{\alpha+\beta}=e_\alpha\circ e_\beta$$f(n)\le e_\alpha(\mr{poly}(n))$$g(n)\le e_\beta(\mr{poly}(n))$$f(g(n))\le e_{\alpha+\beta}(\mr{poly}(n))$

• $\mr{OMA\text-TIME}(e_\alpha)\cap\mr{coOMA\text-TIME}(e_\alpha)\nsubseteq\mr{P/poly}$ para qualquer .$\alpha>0$

  Esboço de prova: suponha o contrário. Corrija um número inteiro modo que . Deixe-me abreviar Por preenchimento, temos para qualquer . Além disso, usando, por exemplo, o Lemma 11 de Santhanam acima, temos a implicação Como trivialmente , um aplicativo repetido de (1) e (2) mostra ,$k$$1/k<\alpha$

  $$\mr{OcOMT}(f)=\mr{OMA\text-TIME}(\mr{poly}(f(\mr{poly}(n)))\cap\mr{coOMA\text-TIME}(\mr{poly}(f(\mr{poly}(n))).$$ $$\tag{1}\mr{OcOMT}(e_{\beta+1/k})\subseteq\mr{SIZE}(e_\beta(\mr{poly}(n)))$$ $\beta\ge0$ $$\tag{2}\mr{PSPACE\subseteq SIZE}(e_\beta(\mr{poly}(n)))\implies\mr{PSPACE\subseteq OcOMT}(e_\beta).$$ $\mr{PSPACE\subseteq OcOMT}(e_1)$$\mr{PSPACE\subseteq SIZE}(e_{(k-1)/k}(\mr{poly}(n)))$$\mr{PSPACE\subseteq OcOMT}(e_{(k-1)/k})$ , , e assim por diante. Após etapas, alcançamos Usando o padding mais uma vez, obtemos que contradiz os resultados acima , como é um limite superpolinomial.$\mr{PSPACE\subseteq SIZE}(e_{(k-2)/k}(\mr{poly}(n)))$$\mr{PSPACE\subseteq OcOMT}(e_{(k-2)/k})$$k$ $$\mr{PSPACE\subseteq P/poly}\qquad\text{and}\qquad\mr{PSPACE=OMA\cap coOMA}.$$ $$\mr{DSPACE}(e_{1/k})\subseteq\mr{OcOMT}(e_{1/k})\subseteq\mr{P/poly},$$ $e_{1/k}$

Como ninguém postou uma resposta, eu mesmo responderei a pergunta com os comentários postados na pergunta original. Agradecimentos a Robin Kothari, Emil Jerabek, Andrew Morgan e Alex Golovnev.

$MA_{exp}$ parece ser a menor classe uniforme com limites inferiores superpolinomiais conhecidos.

$O_2^P$ parece ser a menor classe conhecida que não possui circuitos de tamanho para cada fixo .$n^k$$k$

Por diagonalização, segue-se que para qualquer função super polinomial (e construtível em espaço) , o não possui circuitos de tamanho polinomial. versus ainda está aberto.$s$$DSPACE[s(n)]$$PSPACE$$P/poly$

$P/poly$ é fechado sob complemento, portanto, contém se e somente se contém .$NEXP$$coNEXP$

Por favor me corrijam se eu estiver errado, mas tanto quanto eu posso dizer, nós realmente não sabemos o tamanho fixo-polinomial limite inferior para . Isso ocorre porque o argumento usual de Karp-Lipton não passa por , pois não sabemos se (na verdade, isso é equivalente a perguntar se ). No entanto, sabemos que não está contido em para qualquer , como mostrado por Chakaravarthy e Roy.$O_2^P$$O_2^P$$\textsf{NP}\subseteq O_2^P$$\textsf{NP}\subseteq \textsf{P/poly}$$\textsf{NP}^{O_2^P}$$\textsf{SIZE}(n^k)$$k$