Problemas en NP pero no en Promedio-P / poli

El Theoem de Karp-Lipton establece que si , entonces P H colapsa a Σ P 2 . Por lo tanto, suponiendo separaciones entre Σ P 2 y Σ P 3 , ningún problema completo de N P pertenecerá a P / p o l y .$\mathsf{NP} \subset \mathsf{P/poly}$$\mathsf{PH}$$\mathsf{\Sigma^P_2}$$\mathsf{\Sigma^P_2}$$\mathsf{\Sigma^P_3}$$\mathsf{NP}$$\mathsf{P/poly}$

Estoy interesado en la siguiente pregunta:

Suponiendo que no colapsa, o asumiendo cualquier otra suposición razonable en la complejidad estructural, se ha comprobado que los problemas de N P difíciles de resolver no están en A v e r a g e - P / p o l y (si los hay )?$\mathsf{PH}$ $\mathsf{NP}$$\mathsf{Average\mbox{-}P/poly}$

Se puede encontrar una definición de en Relaciones entre la complejidad del caso promedio y la del peor caso . Gracias a Tsuyoshi por señalar que realmente necesito usar A v e r a g e - P / p o l y en lugar de P / p o l y .$\mathsf{Average\mbox{-}P/poly}$$\mathsf{Average\mbox{-}P/poly}$$\mathsf{P/poly}$

Creo que hay problemas como (las versiones de decisión de) FACTORING o DLOG que se conjeturan en , pero la conjetura no está probada en base a separaciones entre Clases de complejidad. (Por favor corrígeme si estoy equivocado.)$\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$

Esta es una versión ligeramente mejorada de mis dos comentarios sobre la pregunta combinada.

Limitemos nuestra atención a los problemas de distribución en DistNP (también conocido como (NP, P-computable)) por simplicidad. Entonces está buscando un problema en DistNP ∖ Promedio-P / poli. Tautológicamente, tal problema existe si y solo si DistNP ⊈ Promedio-P / poli. Y si DistNP ⊈ Promedio-P / poli, entonces cada problema de DistNP completo se encuentra fuera de Promedio-P / poli porque Promedio-P / poli está cerrado bajo reducciones de mayúsculas y minúsculas.

(Considerando un SampNP de clase más grande (también conocido como (NP, muestra de P) ) en lugar de DistNP no cambia mucho la situación porque DistNP ⊆ Promedio-P / poli si y solo si SampNP ⊆ Promedio-P / poli. Esta equivalencia es directa Corolario del resultado de Impagliazzo y Levin [IL90] de que cada problema de distribución en SampNP es reducible en un caso promedio a algún problema de distribución en DistNP).

No sé qué suposición natural implica DistNP ⊈ Promedio-P / poli. La suposición de que la jerarquía polinómica no colapsa no se sabe que implica una consecuencia aún más débil que DistNP ⊈ Promedio-P, de acuerdo con la Sección 18.4 de Arora y Barak [AB09]: “[…] aunque sabemos que si P = NP , entonces la jerarquía polinómica PH colapsa a P [...], no tenemos un resultado análogo para la complejidad promedio de los casos ".

Referencias

[AB09] Sanjeev Arora y Boaz Barak. Complejidad computacional: un enfoque moderno , Cambridge University Press, 2009.

[IL90] Russell Impagliazzo y Leonid A. Levin. No hay mejores maneras de generar instancias NP difíciles que elegir de manera uniforme al azar. En el 31º Simposio anual sobre fundamentos de la informática , 812–821, octubre de 1990. http://dx.doi.org/10.1109/FSCS.1990.89604