Peut-on amplifier P = NP au-delà de P = PH?

54

Dans la complexité descriptive , Immerman a

Corollaire 7.23. Les conditions suivantes sont équivalentes:
1. P = NP.
2. Structures sur finies et ordonnées, FO (LFP) = SO.

Cela peut être considéré comme "amplifiant" P = NP en une déclaration équivalente sur (probablement) des classes de complexité plus grandes. Notez que SO capture la hiérarchie temps polynomial PH et que FO (LFP) capture P, ce qui peut être considéré comme P = NP ssi P = PH.

(La partie intéressante de ceci est l'affirmation que P = NP implique P = PH; il est trivial que P = CC implique P = NP pour toute classe CC contenant NP. Immerman se contente de dire "si P = NP, alors PH = NP" , vraisemblablement parce que P = NP peut être utilisé avec la définition de PH de Oracle pour montrer par induction que toute la hiérarchie s’effondre.)

Ma question est:

Jusqu'où peut-on amplifier P = NP de cette façon?

En particulier, quelle est la plus grande classe connue CC 'telle que P = NP implique P = CC' et la plus petite classe CC telle que P = NP implique CC = NP? Cela permettrait de remplacer P = NP par la question équivalente CC = CC '. P semble être une classe assez puissante, qui semble offrir peu de marge de manœuvre pour les arguments qui tentent de la séparer de NP: dans quelle mesure la marge de manœuvre peut-elle être amplifiée?

Bien entendu, un argument montrant que P = PH est la limite de cette approche m'intéresserait également.


Edit: notez la question étroitement liée Pourquoi P = NP n'implique-t-il pas P = AP (c'est-à-dire P = PSPACE)? qui se concentre sur l’autre direction, pourquoi nous n’avons pas de preuves que P = PSPACE. Dans leurs réponses, Kaveh et Peter Shor soutiennent que le nombre d’alternations à fixer est essentiel. Une autre question connexe est Un problème de décision dont on ne sait pas qu'il est dans PH mais qui sera dans P si P = NP qui demande un problème candidat; les réponses peuvent également être utilisées pour construire des réponses à cette question, bien que ces classes soient quelque peu artificielles (merci à Tsuyoshi Ito de l'avoir signalé). Dans un contexte plus général, effondrement de la machine de turing limitée par alternance et temps alternatif demande si un effondrement local à un niveau quelconque dans une hiérarchie d'alternance induit un effondrement vers le haut, comme cela se produit avec la hiérarchie polynomiale.

András Salamon
la source
12
Connexes (promotion personnelle sans scrupule): Un problème de décision dont on ne sait pas qu'il est dans PH mais qui sera dans P si P = NP .
Tsuyoshi Ito
17
Comme une façon de formaliser ce que les langues sont en P si P = NP, Regan introduit la classe de complexité H. Un langage est dans H si et seulement si L est P O par rapport à chaque oracle O pour que P O = NP O . Ainsi, L est dans H si l'énoncé P = NPLOOOOL P relativise. PH H Alternations-time (L . D'après le théorème de Toda et quelques-uns des lemmes du théorème de Toda, il est également vrai que H P m o d q P pour tout q . (Fondamentalement, tout oracle satisfaisant P O = NP O donne une nouvelle limite supérieure sur H. Il est possible d'indiquer si H = PH.)(O(loglogn),poly)modqPqOO
Russell Impagliazzo
4
@ Russell: merci! Ce commentaire ressemble à une réponse.
András Salamon Le
5
Nous avons enfin trouvé une référence à la classe de Ken Regan : voir la définition 6.3 de "Ensembles d'index et présentations de classes de complexité", disponible à l' adresse suivante : citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Version officielle sur: dx.doi.org/10.1016/0304-3975(95)00146-8H
Joshua Grochow
3
Soit f (n) une fonction non bornée. H ne figure pas dans Alternations-Time (f (n), poly) et si vous pouviez prouver que P = NP implique que P = Alternations-Time (f (n), poly), alors NP est différent de L.
Lance Fortnow

Réponses:

6

Commentaire de Russell Impagliazzo :

Afin de formaliser les langues en si P = N P , Regan a introduit la classe de complexité HPP=NPH . Un langage est H si et seulement si L est P O par rapport à chaque oracle O de telle sorte que P O = N P O . Ainsi, L est dans H si l'énoncé P = N PLHLPOOPO=NPOLH relativise. P HHA l t T i m e ( O (P=NPLP . D'après le théorème de Toda et quelques-uns des lemmes du théorème de Toda, il est également vrai que HP m o d q P pour tout q . Fondamentalement, tout oracle satisfaisant à P O = N P O donne une nouvelle limite supérieure surPHHAltTime(O(lglgn),poly)HPmodqPqPO=NPO . Il est ouvert si H = P H .HH=PH

Et du commentaire de Lance Fortnow :

Soit une fonction non bornée. H ne figure pas dans A l t T i m e ( f ( n )f(n)H et si on pouvait prouver P = N P implique P = A l t T i m e ( f ( n ) , p o l y ) puis NAltTime(f(n),poly)P=NPP=AltTime(f(n),poly) est différent de L .NPL

Pour la définition de voir définition 6.3 dansH

Kaveh
la source
1
@Josh, en ce qui concerne le commentaire de Lance, j’ai le sentiment que quelque chose me manque, car n’est pas limité et AltTime (f, poly) contient H conformément au commentaire de Russel. f(n)=lglgn
Kaveh
3
Je suis confus à propos de quelque chose. Pourquoi la réponse de Josh Grochow à la question précédente sur ce sujet ( cstheory.stackexchange.com/a/2039/1575 ) ne répond-elle pas essentiellement à la question de Regan? C'est-à-dire pourquoi ne donne-t-il pas l'exemple d'un langage L qui est dans P si P = NP par un argument relativisant, mais ce n'est pas dans PH si P! = NP? Et pourquoi ne montre-t-il donc pas que si P! = NP, H est strictement supérieur à PH?
Scott Aaronson
3
En fait, une réponse possible m'est donnée. Le problème est-il que, dans la construction de Grochow, la définition même du langage L dépendra de l'oracle O?
Scott Aaronson
1
@ Scott: En effet, votre réponse possible est correcte, car les chaînes utilisées pour la diagonalisation (et le fait de savoir si elles sont placées dans ou hors de L) dépendent de l'oracle. Plus en détail, si , le langage L est fini, donc les différents LPO=NPOLL pour différents ne sont que finement différents. Mais si l' on considère tous les O tels que P ON P O , le L pour ces différentes O ne peut pas être même p équivalent, étant donné que cet ensemble de sous - ensemble est un Oracles dense de 2 Σ * .OOPONPOLO2Σ
Joshua Grochow
5

Comme je l'ai écrit dans ma réponse à l'autre question, rendons l'argument constructif et uniforme dans le nombre d'alternances en donnant un algorithme qui résout supposant que nous ayons un algorithme polynomial pour SAT et voyons ce que nous obtiendrions si k n'est pas constant.ΣkPk

Soit un DTM à deux entrées x et y . Pensez-y comme un vérificateur pour un problème N P.MxyNP

Cook(M,n,t)Ms(n,t)polyMnt

P=NPAppoly

siisi+1=sp(si)kq(n)=(sp)k(n)n est la taille de la formule TQBF donnée en entrée.

kq(n)polyP

kω(1)q(n)n2O(k)k=lglgnk=lgn


C

TP=NPP=C
TZFCPNP

CHHPP=NP


BPP=PPIP=PSpace

Je trouve aussi l'idée qu'il n'y a qu'une seule façon correcte de relativiser une problématique de classe de complexité, ce qui cause beaucoup d'idées fausses (comme penser la relativisation en tant qu'opération fonctionnelle sur les classes de complexité dans leur sens extensional, une relativisation est une modification d'un modèle de calcul , pas une classe de fonctions ou de langues). Je pense que voir les relativisations comme des cadres de calcul modifiés (interactifs) est plus utile. De cette façon, il existe de nombreuses manières utiles de relativiser une classe de complexité (dans son sens intentionnel). Pour obtenir des informations sur le paramètre non relativisé à partir d'un cadre relativisé, nous avons besoin d'un principe de transfert similaire à celui utilisé dans l'analyse non standard.. Notez que choisir une méthode de relativisation particulière pour les classes qui préservent les relations connues entre les classes ne nous donne pas un principe de transfert (c’est le principal critère généralement utilisé dans la littérature pour décider de ce qui est "la" relativisation correcte d’une classe).

Kaveh
la source
Je suis d’accord avec le fait que "voir les relativisations comme un cadre de calcul interactif est plus utile à mon avis" d’une certaine manière. À savoir, la présentation des relativisations pourrait être rendue plus intuitive pour comprendre en commençant par la situation où la ou les machines (avec accès interactif à Oracle) sont données en premier, et où un adversaire est autorisé à sélectionner une langue pour Oracle. Ensuite, on passe à la situation où un langage oracle (complexe) est donné en premier, et les machines peuvent maintenant être adaptées au monde donné par l'oracle spécifique.
Thomas Klimpel