Les quartiers accueillants de «P» et de «NP-hard»

Soit une tâche algorithmique. (Cela peut être un problème de décision ou un problème d'optimisation ou toute autre tâche.) Appelons "du côté polynomial" si supposer que est NP-difficile est connu pour impliquer que la hiérarchie polynomiale s'effondre. Appelons "du côté de NP" si nous supposons que admet qu'un algorithme polynomial est connu pour impliquer que la hiérarchie polynomiale s'effondre.$X$$X$$X$$X$$X$

Bien sûr, chaque problème dans P est du côté polynomial et tout problème qui est NP-difficile est du côté NP. Aussi, par exemple, la factorisation (ou n'importe quoi dans le coNP d'intersection de NP) est du côté polynomial. L'isomorphisme graphique est du côté polynomial. QUANTUM-SAMPLING se situe du côté NP.

1) Je suis intéressé par plus d'exemples (aussi naturels que possible) de tâches algoritmiques du côté polynomial et (surtout) par davantage d'exemples du côté NP.

2) Naïvement, il semblerait que la partie NP soit une sorte de "voisinage" des problèmes difficiles à résoudre, et la partie P est un "voisinage de P". Est-ce une bonne idée de considérer les problèmes du côté NP comme "considérablement plus difficiles" par rapport aux problèmes du côté P. Ou même de considérer les problèmes du NP comme "moralement NP-difficiles?"

3) (Cela peut sembler évident, mais je ne le vois pas) Y at-il un deux côtés ou existe-t-il des raisons théoriques de croire qu’un tel est improbable? Mise à jour La réponse est OUI; voir la réponse de Yuval Filmus ci-dessous.$X$$X$

(Si ces "côtés" sont liés à des classes de complexité réelles et si je manque un jargon pertinent ou des résultats pertinents, veuillez le faire savoir.)

Mise à jour:Il existe maintenant plusieurs très bonnes réponses à la question. Comme Yuval Filmus l’a signalé en premier lieu, la question n’est pas formelle et l’argument montrant que X est du côté P ou du côté NP est nécessaire. (Sinon, vous pouvez avoir pour tâche de présenter une preuve pour 0 = 1 qui est des deux côtés.) En mettant cela de côté, il se peut que les problèmes X (véritablement) du côté NP capturent d'une manière ou d'une autre la dureté. SAT, bien que cela puisse également être le cas pour certains problèmes du côté P où la dureté de SAT est affaiblie (même légèrement) de manière prouvable. Yuval Filmus a donné une version affaiblie de SAT qui est des deux côtés. Andy Drucker a donné (en deux réponses) cinq exemples intéressants, dont une référence aux hiérarchies basse et haute de Schöning, et Scott Aaronson a donné d'autres exemples intéressants. a évoqué la question de l'inversion d'une fonction unidirectionnelle proche de la dureté du NP et pourtant du côté P, et sa réponse aborde également le cas intéressant de QUANTUMSAMPLING. J'ai mentionné un vieux résultat de ce genre chez Feige et Lund.

Les termes mêmes "du côté P" et "du côté NP", et bien sûr le titre de la question, nous incitent à imaginer un "quartier confortable" entourant P et un autre "quartier confortable" entourant les problèmes difficiles du NP. Cependant, je voudrais dire que ces deux quartiers ne sont pas du tout "confortables"!

Comme première observation, il existe des problèmes "du côté P" qui semblent "moralement" beaucoup plus proches de NP-difficile que de P. Un exemple, bien sûr, anticipé par Gil, est le problème général de l'inversion des fonctions à sens unique ( en fonction du type de réduction autorisé, voir Bogdanov-Trevisan ou Akavia et al.).

Inversement, il existe également des problèmes "du côté du NP" qui semblent "arbitrairement loin" d'être NP-difficiles. Un exemple stupide est un langage aléatoire L, avec une probabilité de 1 sur L! Car si un tel L est dans P, alors 0 = 1 et les maths sont incohérents, et donc PH s'effondrera également. ;-RÉ

(Notez qu'un langage aléatoire L est aussi "du côté P", avec une probabilité de 1 sur L. Car presque tous ces L ont la propriété que s'ils sont NP-durs, alors NP⊆BPP et PH s'effondrent. Et ceci fournit une preuve, beaucoup plus simple que l'appel au théorème de Ladner, qu'il existe des langues des deux "côtés". sont des deux côtés!)

Cela ressemble à du jeu juvénile, mais je voudrais en tirer une leçon sérieuse. Je dirais que, même si QUANTUM SAMPLING est formellement "du côté NP", ce problème est à peine plus proche d'une "moralité NP-difficile" que le langage aléatoire L ne l'était. Arkhipov et moi (et indépendamment Bremner-Jozsa-Shepherd) avons montré que, si QUANTUM SAMPLING est dans P (ou plutôt, dans SampBPP, la classe des problèmes d'échantillonnage résolvables de manière polynomiale), alors P ^#P = BPP ^NP , et donc le la hiérarchie polynomiale s'effondre. Cependant, si vous êtes une machine BPP, un oracle pour BosonSampling ne vous apporterait, à notre connaissance, aucun moyen de résoudre un problème NP-complet au maximum qu'un oracle aléatoire. Seulement si vous avez déjà la capacité de résoudre des problèmes NP-complets - par exemple,Machine ^NP - remarquez-vous que l’oracle BosonSampling améliore encore vos capacités, jusqu’à #P. Mais la propriété d'augmenter NP jusqu'à #P semble différente de, et peut-être même "orthogonale à", la propriété d'être NP-dur par soi-même.

Par ailleurs, la question de Gil a suggéré un problème ouvert merveilleux, à savoir si BosonSampling est également "de la partie P." Autrement dit, pouvons-nous montrer que si NP se réduit à BosonSampling, le pH s'effondre? Bien que je puisse manquer quelque chose d'évident, à première vue, je ne sais pas comment prouver une chose pareille, pas plus que je ne saurais prouver l'implication plus forte que si NP ⊆ BQP, le pH s'effondre.

Deux commentaires, qui ne constituent ni l'un ni l'autre une réponse, mais qui peuvent apporter une lecture utile.

1) Schöning a défini deux classes de problèmes NP, appelées «hiérarchie basse» et «hiérarchie haute», qui sont liées à vos notions. En particulier, les problèmes dans LowH sont "du côté P" et les problèmes dans HighH sont du côté NP. Un certain nombre de résultats de complexité connus peuvent être énoncés dans ce cadre. Par exemple, le théorème de Karp-Lipton dit que NP n'est pas dans P / poly sauf si le PH s'effondre; ceci est une conséquence du fait que NP P / poly est contenu dans un niveau fixe de LowH (comme le montre la technique de Karp-Lipton). Notez que nous ne prévoyons pas que NP ∩ P / poly, ou LowH, figure dans P. Pour une enquête sur LowH en particulier, voir$\cap$$\cap$

http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Abstracts/low.ps.abstr_html

2) Considérons le problème qui nous donne une table de vérité complète d’une fonction booléenne, et demande si elle a un circuit booléen d’une certaine taille . Ce problème est dans NP, et peu probable dans P (cela impliquerait plusieurs conséquences surprenantes). D'autre part, une preuve de NP-complétude de ce problème, s'il obéissait à certaines restrictions assez naturelles, nous donnerait de nouveaux résultats puissants en théorie de la complexité. Cela a été montré par Kabanets et Cai dans$t$

http://eccc.hpi-web.de/report/1999/045/

Pour être clair, il n'y a aucune preuve réelle que ce problème n'est pas si difficile à résoudre , ou qu'il soit facile en aucun sens. Mais cela semble assez différent des autres problèmes difficiles du NP. Je pense que cela fait partie des candidats les plus intéressants pour les problèmes NP-intermédiaires, et non des candidats connus.

La preuve du théorème de Ladner par Russell Impagliazzo fournit un exemple pour 3. Par souci d'exhaustivité, je copie ci-dessous la définition de la tâche algorithmique et j'esquisse la preuve qu'il s'agit "des deux côtés", au sens fort: dans les deux cas, PH effondrements de P. Plus de détails se trouvent dans la note liée (tirée de blog de Fortnow et Gasarch), qui est (légèrement) adapté de l'annexe à uniformément dur Sets par Downey et Fortnow.$X$

Que une énumération de tous les cadencé machines de Turing de polynomial, de telle sorte que M i se termine dans le temps n log log i . Dans la suite, nous mentionnerons des paires ( α , β ) . Celles-ci sont supposées être codées sous forme de chaînes binaires de manière raisonnable.$M_i$$M_i$$n^{\log\log i}$$(\alpha,\beta)$

Nous définissons récursivement une fonction . Tout d'abord, f ( 1 ) = 1 . Soit f ( n ) , f ( n + 1 ) est défini comme suit. Soit X n se composent de toutes les paires ( φ , 1 | φ | f ( | φ | ) ) de telle sorte que | & phiv | ≤ n et $f(n)$$f(1) = 1$$f(n)$$f(n+1)$$X_n$$(\phi,1^{|\phi|^{f(|\phi|)}})$$|\phi| \leq n$$\phi$est une formule satisfiable. S'il y a une chaîne binaire de longueur au plus log n de telle sorte que x ∈ L ( M f ( n ) ) △ X n alors f ( n + 1 ) = f ( n ) + 1 , sinon f ( n + 1 ) = f ( n ) . Il n’est pas difficile de vérifier que f ( n $x$$\log n$$x \in L(M_{f(n)}) \triangle X_n$$f(n+1) = f(n)+1$$f(n+1) = f(n)$$f(n)$peut être calculé en polynôme temporel en .$n$

Enfin, nous pouvons définir la tâche algorithmique : il se compose de toutes les paires ( φ , 1 | φ | f ( | φ | ) ) pour laquelle φ est un CNF satisfiable. Notez que X = ⋃ n X n .$X$$(\phi,1^{|\phi|^{f(|\phi|)}})$$\phi$$X = \bigcup_n X_n$

Si avait un algorithme polytime M i, alors f ( n ) ≤ i pour tout n et ainsi M i peut être utilisé pour résoudre SAT.$X$$M_i$$f(n) \leq i$$n$$M_i$

Ensuite, supposons qu'il y ait une réduction polytime de SAT à X , en prenant le temps n k . Si X avait un algorithme polynomial puis comme nous l' avons vu PH se réduit à P. Dans le cas contraire, f ( n ) ⟶ ∞ , et en particulier, f ( n ) > k pour n ≥ n 0 . La réduction g prend ainsi toute instance de SAT de taille plus grande que n 0 et soit réduit à un petit exemple, ou en sortie une chaîne de caractères qui ne sont pas de la forme ( φ $g$$X$$n^k$$X$$f(n) \longrightarrow \infty$$f(n) > k$$n \geq n_0$$g$$n_0$ ; ce dernier cas peut être reconnu en polytime puisque f est polytime. En itérant g , nous obtenons un algorithme polytime pour SAT.$(\phi,1^{|\phi|^{f(|\phi|)}})$$f$$g$

L'hypothèse selon laquelle la hiérarchie polynomiale ne s'effondre pas a été l'une des voies de découverte les plus fertiles de la théorie de la complexité. Bon nombre de ces résultats peuvent être formulés comme indiquant que des tâches algorithmiques spécifiques sont "du côté P" ou "du côté NP". non-effondrement de P H semble avoir beaucoup plus de conséquences que l'hypothèse plus faible P ≠ N P , et il serait impossible de les regrouper dans un seul poste bref. Permettez-moi de donner trois exemples qui donnent une petite idée de la variété de ce travail.$PH$$P \neq NP$

$SAT$$NP$$SAT$$P = NP$

http://people.cs.uchicago.edu/~fortnow/papers/2q.pdf

$SAT$$\psi$$m$$n \ll m$$\psi$$n$$m$$SAT$

En réponse à une question de Bodlaender, Downey, Fellows et Hermelin, Fortnow et Santhanam ont montré qu'une telle réduction de compression est improbable, car elle effondrerait la hiérarchie poly:

http://people.cs.uchicago.edu/~fortnow/papers/compress.pdf

Leur résultat s’applique à des réductions aléatoires permettant des erreurs unilatérales. J'ai prouvé un résultat correspondant pour une erreur bilatérale dans

http://eccc.hpi-web.de/report/2012/112/

(Chacun de ces documents donne en réalité des informations plus fortes et plus spécifiques que les résultats cités ci-dessus.)

$PH$$PPAD$$PH$$A$$PPAD^A$$TFNP^A$$PH^A$

http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf

$X$$P$ $\Rightarrow$ $PH$$PH$

Je suis tombé sur ce résultat de Feige et Lund qui montre que si la hiérarchie polynomiale ne s'effondre pas, il est difficile de deviner des informations, même très partielles, sur le permanent d'une matrice aléatoire.

Uriel Feige et Carsten Lund, De la dureté à calculer le permanent de matrices aléatoires. Complexité informatique 6 (1996/1997) 101-132.

Permettez-moi également de mentionner deux autres résultats pertinents portés à mon attention par Uri Feige:

Les deux articles suivants l’appliquent dans le contexte de la kernelisation (algorithmes traitable à paramètre fixe).

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: Sur les problèmes sans noyaux polynomiaux. J. Comput. Syst. Sci. 75 (8): 423-434 (2009)

Lance Fortnow, Rahul Santhanam: Infaisabilité de la compression d'instances et de PCP succincts pour NP. J. Comput. Syst. Sci. 77 (1): 91-106 (2011)