Versión no uniforme para toda la jerarquía polinómica.

Las versiones no uniformes de P, NP y coNP son P / poly, NP / poly y coNP / poly. Del mismo modo, podemos definir una versión no uniforme para cada nivel en el PH.

Por ejemplo: / poly consiste en problemas de la forma , donde C es un circuito de tamaño polinómico que puede variar según la longitud de la cadena de entrada , e también tienen longitudes polinómicas en . $\Sigma_2$ $\{x : \exists y \forall z \; C(x,y,z)\}$ $x$ $y,z$ $x$

Al hacer esto para todos los niveles de PH, obtenemos una versión no uniforme de PH / poly.

PREGUNTAS: ¿Hay algo conocido sobre esta jerarquía? ¿Se derrumba? ¿O hay otro nombre para él en la literatura?

cc.complexity-theory complexity-classes polynomial-hierarchy Danny Nguyen
fuente

Respuestas:

Bueno, claro, sabemos cosas. Creo que esta es una nomenclatura bastante estándar para ello. Esta jerarquía colapsa si y solo si hace, ejercicio: $\mathsf{PH}$

Para una dirección, modifique la prueba de Karp-Lipton para mostrar que si entonces colapsa, y observe que este resultado se relativiza $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ $\mathsf{PH}$
Para la otra dirección, vea los comentarios de Kaveh a continuación.

Joshua Grochow
fuente

¿Puede colapsar pero no colapsar?

P H

$\mathsf{PH}$

n u P H

$\mathsf{nuPH}$

Daniel Apon

@Daniel, creo que puedes deshacerte de la uniformidad de los cuantificadores en el circuito, así que sí, si PH los colapsa, también lo hace nuPH.

Kaveh

@Kaveh: ¿Cómo? Puede que esté siendo lento, pero aún no lo veo ...

Joshua Grochow

Suponga que P = NP. Considere L en PH / poli. Supongamos que L / poly, es decir para alguna función de consejo f poly y L' está en . Pero L 'está en P, por lo tanto, L está en P / poli.

\in

$\in$

Σ_{k}^{P}

$\Sigma^P_k$

χ_{L} (x) = χ_{L^{'}} (x, f (| x |))

$\chi_L(x) = \chi_{L'}(x,f(|x|))$

\in

$\in$

Σ_{k}^{P}

$\Sigma^P_k$

Kaveh

Probablemente sea mejor quedarse con : D

P H / p o l y

$\mathsf{PH/poly}$

Daniel Apon