Condiciones suficientes para el colapso de la Jerarquía Polinómica (PH)

¿Cuáles son algunas afirmaciones (no conocidas) de que si es cierto, el PH debe colapsar?

Se agradecen las respuestas que contienen una afirmación corta de alto nivel con referencia (s). Traté de hacer una búsqueda inversa sin mucha suerte.

Hay un número (creciente) de resultados de complejidad parametrizados donde la existencia de una kernelización de tamaño polinómico implica el colapso del PH al tercer nivel. La técnica central se da en [1], basándose en trabajos previos (referenciados en [1]).

Como ejemplo simple, el problema -Path es la versión parametrizada del problema de la ruta más larga:$k$

$k$ -Path Instance : un gráfico y entero . Parámetro : . Pregunta : ¿ contiene una ruta de longitud ? G k k G k
$G$$k$
$k$
$G$$k$

Este problema está en FPT (con algoritmos algo prácticos), pero en [2] muestran que si tiene un núcleo de tamaño polinómico (en ), entonces el PH colapsa a . (La presentación actual generalmente está redactada como un resultado de kernalización negativo a menos que NP coNP / poly o coNP NP / poly, por lo que buscar algo como "sin núcleo polinomial a menos que" obtenga muchos resultados).Σ P 3 ⊆ $k$$\Sigma^{P}_{3}$$\subseteq$$\subseteq$

Referencias

1. HL Bodlaender, BMP Jansen y S. Kratsch, "Límites inferiores de kernelization por composición cruzada", SIAM J. Discrete Math., 28 (2014), pp. 277–305. [versión arXiv]
2. HL Bodlaender, RG Downey, MR Fellows, D. Hermelin, "Sobre problemas sin núcleos polinomiales", Journal of Computer and System Sciences, 75 (8): 423-434. 2009. [Versión alojada de Stanford]

Aquí hay otra condición interesante bajo la cual la jerarquía polinómica se colapsa al tercer nivel: supongamos que un lenguaje NP-completo tiene una auto reducción aleatoria (no adaptativa), luego la jerarquía polinómica se colapsa a . Como referencia: mira las notas de Luca Trevisan . (Teorema 67)$\Sigma_{3}^{P}$

Otra condición interesante es esta:

Sabemos que aproximar está en B P P N P (Ahora B P P en Σ P 2 hace aproximar # 3 S A T en Σ P 3 ).$\#3SAT$$BPP^{NP}$$BPP$$\Sigma_2^{P}$$\#3SAT$$\Sigma_3^{P}$

Además, el teorema de De Toda, .$PH \subseteq P^{\#P}$

Combinando estos dos, obtenemos: Si aproximar es equivalente a calcular exactamente # 3 S A T , entonces la Jerarquía Polinómica se colapsa.$\#3SAT$$\#3SAT$

Referencias

[1] Jim Kadin, La jerarquía del tiempo polinomial se derrumba si la jerarquía booleana se derrumba , SIAM Journal on Computing 17 (1988), no. 6, págs. 1263-1282, doi: 10.1137 / 0217080 .

[2] Richard Chang y Jim Kadin, La jerarquía booleana y la jerarquía polinómica: una conexión más estrecha , SIAM Journal on Computing 25 (1996), no. 2, págs. 340–354, doi: 10.1137 / S0097539790178069 .

$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}=\mathsf{UP}$$\mathsf{PH}$

$L \in \mathsf{NP}$$\varphi$$\varphi$$x$$(\varphi,x) \in L$$\varphi$ $x$$(\varphi,x) \in L$$\mathsf{PH}$

Otra formalización es:

$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$$\mathsf{PH}$

$A := \forall i , \Sigma^{P}_{i} \neq \Pi^{P}_{i}$$\mathbb{PH}$$A \implies B$

$\bar{B} \implies \bar{A}$$\mathbb{PH}$

1. $\mathbb{PH}$
2. $\mathbb{PH}$

$\mathbb{PH}$

Aquí hay algunos sucintos:

1. $PSPACE \subseteq P/poly$
2. $EXP \subseteq P/poly$
3. $NP \subseteq P/log$