Problèmes en NP mais pas en Moyenne-P / poly

20

Le théorème de Karp – Lipton déclare que si , alors s'effondre en . Par conséquent, en supposant des séparations entre et , aucun problème complet n'appartiendra à .P H Σ P 2 Σ P 2 Σ P 3 N P P / p o l yNPP/polyPHΣ2PΣ2PΣ3PNPP/poly

Je m'intéresse à la question suivante:

En supposant que ne s'effondre pas, ou en supposant toute autre hypothèse raisonnable de complexité structurelle, quels problèmes difficiles en moyenne se sont avérés ne pas résider dans (le cas échéant)?N P A v e r a g e - P / p o l yPH NPAverage-P/poly

Une définition de peut être trouvée dans les relations entre la complexité du cas moyen et celle du pire . Merci à Tsuyoshi d'avoir souligné que j'ai en fait besoin d'utiliser au lieu de .A v e r a g e - P / p o l y P / p o l yAverage-P/polyAverage-P/polyP/poly

Je pense qu'il y a des problèmes tels que (les versions de décision de) FACTORING ou DLOG qui sont supposés résider dans , mais la conjecture n'est pas prouvée sur la base de séparations entre classes de complexité. (Corrigez-moi si j'ai tort, s'il-vous plait.)NPAverage-P/poly

MS Dousti
la source
2
(1) Je ne pense pas que l'hypothèse selon laquelle la hiérarchie polynomiale ne s'effondre pas est connue pour impliquer qu'il existe un problème difficile en moyenne dans NP. La section 18.4 d'Arora et Barak déclare: «[…] même si nous savons que si P = NP, alors la hiérarchie polynomiale PH s'effondre en P […], nous n'avons pas de résultat analogue pour la complexité moyenne des cas.»
Tsuyoshi Ito
3
(2) Est-ce que le P / poly dans la question est celui qui présente la complexité du pire cas, ou envisagez-vous un analogue du cas moyen? Si c'est le pire des cas, alors vous avez besoin à la fois de DistP ≠ DistNP et de NP⊈P / poly pour avoir un tel problème, et si ceux-ci se vérifient, alors chaque problème DistNP-complet satisfait l'exigence car un problème DistNP-complete est nécessairement NP-complet si on jette la distribution d'entrée.
Tsuyoshi Ito
@Tsuyoshi: Merci beaucoup. Vous avez un point sur le pire cas par rapport au cas moyen P / poly. Après une seconde réflexion (sur le problème d'origine), je pense que je dois interpréter P / poly comme une classe de cas moyen .
MS Dousti
J'ai lu la révision 3. Tautologiquement, un tel problème existe si et seulement si DistNP ⊈ Average-P / poly. Et si DistNP ⊈ Moyenne-P / poly, alors chaque problème DistNP-complet se situe en dehors de Moyenne-P / poly parce que Moyenne-P / poly est fermé par des réductions (entre les problèmes de distribution). Mais vous demandez peut-être un problème plus naturel sous une hypothèse plus forte.
Tsuyoshi Ito,
@Tsuyoshi: Merci. Pourriez-vous faire des commentaires une réponse pour que je puisse l'accepter?
MS Dousti

Réponses:

7

Il s'agit d'une version légèrement améliorée de mes deux commentaires sur la question combinée.

Limitons notre attention aux problèmes de distribution dans DistNP (aka (NP, P-computable)) pour plus de simplicité. Ensuite, vous recherchez un problème dans DistNP ∖ Moyenne-P / poly. Tautologiquement, un tel problème existe si et seulement si DistNP ⊈ Moyenne-P / poly. Et si DistNP ⊈ Average-P / poly, alors chaque problème DistNP-complete se situe en dehors de Average-P / poly parce que Average-P / poly est fermé sous les réductions de cas moyen.

(Le fait de considérer une classe SampNP plus large (aka (NP, échantillonnable P) ) au lieu de DistNP ne change pas beaucoup la situation car DistNP ⊆ Moyenne-P / poly si et seulement si SampNP ⊆ Moyenne-P / poly. Cette équivalence est une corollaire du résultat d'Impagliazzo et Levin [IL90] selon lequel chaque problème de distribution dans SampNP est réductible en cas moyen à un problème de distribution dans DistNP.)

Je ne sais pas quelle hypothèse naturelle implique DistNP ⊈ Moyenne-P / poly. L'hypothèse selon laquelle la hiérarchie polynomiale ne s'effondre pas n'est pas connue pour impliquer une conséquence encore plus faible que DistNP ⊈ Moyenne-P, selon la section 18.4 d'Arora et Barak [AB09]: «[…] même si nous savons que si P = NP , puis la hiérarchie polynomiale PH s'effondre en P […], nous n'avons pas de résultat analogue pour la complexité moyenne des cas. »

Les références

[AB09] Sanjeev Arora et Boaz Barak. Complexité informatique: une approche moderne , Cambridge University Press, 2009.

[IL90] Russell Impagliazzo et Leonid A. Levin. Il n'y a pas de meilleure façon de générer des instances NP dures que de sélectionner uniformément au hasard. In the 31th Annual Symposium on Foundations of Computer Science , 812–821, octobre 1990. http://dx.doi.org/10.1109/FSCS.1990.89604

Tsuyoshi Ito
la source