P / Poly vs Clases de Complejidad Uniforme

No se sabe si NEXP está contenido en P / poli. De hecho, probar que NEXP no está en P / poli tendría algunas aplicaciones en la desrandomización.

1. ¿Cuál es la clase C uniforme más pequeña para la cual se puede demostrar que C no está contenido en P / poli?

2. ¿Mostrar que co-NEXP no está contenido en P / poly tiene algunas otras consecuencias teóricas de complejidad como en el caso de NEXP vs P / poly?

Nota: Soy consciente de que se sabe que $SP_2$ no está contenido en $Size[n^k]$ para cada constante fija $k$ (Esto también se mostró para MA con 1 bit de consejo). Pero en esta pregunta no me interesan los resultados para fijo $k$. Estoy realmente interesado en clases que son diferentes de P / Poly, incluso si estas clases son muy grandes.

$\let\mr\mathrm$$C$k C P / p o l $C\nsubseteq\mr{SIZE}(n^k)$$k$$C$$\mr{P/poly}$

Permítanme decir que es un enlace superpolinómico si es construible en el tiempo, y . Por ejemplo, es un enlace superpolinómico. De hecho, un ejercicio instructivo muestra que si es una función computable monótona ilimitada, hay un enlace 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)}$

Primero, la diagonalización directa muestra que para cualquier . El mismo argumento da:$\Sigma_4^P\nsubseteq\mr{SIZE}(n^k)$$k$

• Si es un enlace superpolinomial, entonces .Σ 4$f$$\Sigma_4\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Bosquejo de prueba: para cualquier , deje que sea ​​el primer circuito lexicográfico de tamaño que calcule una función booleana en variables no computables por un circuito de tamaño . Entonces, el lenguaje definido por funciona.C n 2 $n$$C_n$n < f ( n ) L x ∈ $2f(n)$$n$$<f(n)$$L$$x\in L\iff C_{|x|}(x)=1$

Una mejora bien conocida establece que para cualquier . Igualmente,$S_2\mr P\nsubseteq\mr{SIZE}(n^k)$$k$

• Si es un enlace superpolinomial, entonces .S 2 - T $f$$S_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Esbozo de prueba: Si no, entonces, en particular, , por lo tanto . Por un argumento de relleno, , quod non .P H = S 2 P Σ 4 - T I M E ( f ( n ) ) ⊆ S 2 - T I M $\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}$

Las clases ajenas lo hacen aún mejor. Teniendo en cuenta la objeción planteada por Apoorva Bhagwat, dejemos . Entonces para cualquier , y el mismo argumento arroja: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$

• Si es un enlace superpolinomial, entonces .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}$

  Esbozo de prueba: Si , entonces por relleno, , lo que implica . Luego procedemos como antes.N P ⊆ P / p o l y P H = O 2 $\mr{NLin\subseteq P/poly}$$\mr{NP\subseteq P/poly}$$\mr{PH}=O_2\mr P$

También hay resultados que involucran MA. El resultado mencionado a menudo de que es una exageración. Santhanam demostró para cualquier , y un argumento similar da:p r o m i s e - M A ∩ p r o m i s e - c o $\mr{MA\text-EXP\nsubseteq P/poly}$

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

• Si es un enlace superpolinomial, entonces p r o m i s e - M A - T I M E ( f ( n ) ) ∩ p r o m i s e - c o M A - T I M E$f$

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

  Boceto de prueba: según el Lema 11 de Santhanam (que es una versión más precisa del hecho estándar de que con un probador PSPACE), hay un lenguaje completo de PSPACE y un oráculo de tiempo múltiple aleatorizado TM tal que en la entrada , solo realiza consultas oracle de longitud; si , entonces acepta con probabilidad ; y si , entonces para cualquier oráculo , acepta con probabilidad . L M x M | x | x ∈ L M L ( x ) 1 x ∉ L $\mr{PSPACE=IP}$$L$$M$$x$$M$$|x|$$x\in L$$M^L(x)$$1$$x\notin L$$A$≤ 1 /$M^A(x)$$\le1/2$

  Para un polinomio monótono adecuado , que sea ​​el problema prometedor definido por Sea una reducción polinómica de a su complemento, y sea el problema de la promesa A = ( A Y E S , A N $p$( x , s ) ∈ A Y E $A=(A_{\mr{YES}},A_{\mr{NO}})$h(x)LB=(B Y E S ,B N

  $$\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}$$ $h(x)$$L$( x , s ) ∈ B Y $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}$$ Si se elige adecuadamente grande, Entonces, supongamos por contradicción que tiene circuitos de tamaño polinómico, digamos, . Supongamos que denota el tamaño del circuito más pequeño que computa en las entradas de longitud , y pon ; más precisamente, EntoncesB ∈ p r o m i s e - M A ( n ) = f - 1$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$s ( n ) L n t p ( s ( n ) ) ) t ( n ) = min { m : p ( s ( n ) ) ≤ f ( m ) } . x ↦ ( x , 1 t ( n )$B\in\mr{SIZE}(n^k)$$s(n)$$L$$n$$t(n)=f^{-1}(p(s(n)))$ $$t(n)=\min\{m:p(s(n))\le f(m)\}.$$ $x\mapsto(x,1^{t(n)})$ es una reducción de a , por lo tanto, , que significa Pero dado que es superpolinomial, tenemos . Esto da una contradicción para suficientemente grande.B L ∈ S I Z $L$$B$s ( n ) ≤ t ( n ) k . f t ( n ) = s ( n $L\in\mr{SIZE}(t(n)^k)$ $$s(n)\le t(n)^k.$$ $f$$t(n)=s(n)^{o(1)}$$n$

Si preferimos un resultado con una versión no prometedora de MA, Miltersen, Vinodchandran y Watanabe demostraron para una media exponencial función . Podemos mejorarlo de dos maneras: primero, se cumple para - límites exponenciales para cualquier constante , y segundo, se cumple para las clases ajenas. Aquí, una función es, más o menos, una función tal que

$$\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$. Vea el documento de Miltersen – Vinodchandran – Watanabe y las referencias en el mismo para la definición precisa; involucra una familia de funciones bien comportadas , , de modo que , , y . Además, si y , entonces . Entonces nosotros tenemos:$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 cualquier .$\alpha>0$

  Bosquejo de prueba: suponga lo contrario. Arregle un entero tal que . Permítanme abreviar Al rellenar, tenemos para cualquier . Además, usando, por ejemplo, el Lema 11 de Santhanam anterior, tenemos la implicación Desde trivialmente , una aplicación repetida de (1) y (2) muestra ,$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})$ , , , y así sucesivamente. Después de pasos, llegamos a Al usar el relleno una vez más, obtenemos que contradice los resultados anteriores , ya que es un enlace 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 nadie publicó una respuesta, responderé la pregunta yo mismo con los comentarios publicados en la pregunta original. Gracias a Robin Kothari, Emil Jerabek, Andrew Morgan y Alex Golovnev.

$MA_{exp}$ parece ser la clase uniforme más pequeña con límites inferiores superpolinomiales conocidos.

$O_2^P$ parece ser la clase más pequeña conocida que no tiene circuitos de tamaño para cada fijo .$n^k$$k$

Por diagonalización, se deduce que para cualquier función súper polinomial (y construible en espacio) , no tiene circuitos de tamaño polinómico. versus todavía está abierto.$s$$DSPACE[s(n)]$$PSPACE$$P/poly$

$P/poly$ está cerrado debajo del complemento, por lo que contiene si y solo si contiene .$NEXP$$coNEXP$

Por favor, corríjanme si me equivoco, pero por lo que puedo decir, que en realidad no conocemos un tamaño fijo-polinomio cota inferior para . Esto se debe a que el argumento habitual de Karp-Lipton no se a , ya que no sabemos si (de hecho, esto es equivalente a preguntar si ). Sin embargo, sabemos que no está contenido en para ninguna , como lo muestran Chakaravarthy y 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$