Conséquences de NP = PSPACE

30

Quelles seraient les conséquences désagréables de NP = PSPACE? Je suis surpris de n'avoir rien trouvé à ce sujet, étant donné que ces cours sont parmi les plus célèbres.

En particulier, cela aurait-il des conséquences sur les classes inférieures?

Denis
la source
4
Corollaire immédiat, ou plutôt reformulation de l'identité: jamais le vérificateur n'a besoin de renvoyer le prouveur!
Alessandro Cosentino

Réponses:

28

Si NP=PSPACE , cela impliquerait:

  • P#P=NP
    Autrement dit, compter les solutions à un problème dansNP serait polytemporaire réductible à la recherche d'une solution unique;

  • PP=NP
    Autrement dit, les algorithmes randomisés en temps polynomial avec une probabilité de réussite arbitrairement proche de 1/2 sont réductibles en temps polynomial en algorithmes randomisés en temps polynomial avec erreur unilatérale, où les instances YES sont acceptées avec une probabilité arbitrairement petite;

  • C'est-à-dire que pour tout problème vérifiable en temps polynomial, la randomisation fournit au mieux une accélération polynomiale (mais ce n'est qu'un corollaire de l'effondrement de la hiérarchie polynomiale);MA=NP

  • C'est-à-dire que tout problème qui peut être résolu par un ordinateur quantique a facilement vérifié les certificats pour ses réponses; ce serait un résultat positif important dans la philosophie de la mécanique quantique, et serait probablement utile aux efforts de construction d'ordinateurs quantiques (pour vérifier qu'ils font ce qu'ils sont censés faire).BQPNP

Tout cela est dû aux confinements des classes sur le côté gauche dans (bien que nous ayons également B Q P P P ).PSPACEBQPPP

Niel de Beaudrap
la source
1
Pouvez - vous pointer vers une référence où implique que B Q PN P . MerciNP=PSPACEBQPNP
Tayfun Pay
2
@TayfunPay Vous voulez essentiellement une référence pour . La référence pour cela est BV97 . Cependant, vous pouvez également prouver que B Q PP P . Voir la conférence suivante pour l'intuition à ce sujet: scottaaronson.com/democritus/lec10.htmlBQPPSPACEBQPPP
Alessandro Cosentino
2
@AlessandroCosentino Oui, je sais que et N PP PP S P A C E . Je suppose que je devais juste être souligné pour secouer ma mémoire! Merci! :)BPPBQPPPPSPACENPPPPSPACE
Tayfun Pay
23

Un point qui a été implicitement mais pas encore explicitement mentionné est que nous obtiendrions . Bien que cela soit équivalent à P H s'effondrant en N P , cela découle directement du fait que P S P A C E est fermé sous complément, ce qui est trivial à prouver.NP=coNPPHNPPSPACE

Je pense que mérite d'être souligné à lui seul en raison du grand nombre de conséquences surprenantes qu'il a: il existe de courtes preuves témoignant lorsqu'un graphique n'est pas tricolore, sont * non * isomorphes, ..., et (dans un certain sens plus généralement) qu'il existe un système de preuve Cook-Reckhow dans lequel chaque tautologie propositionnelle a une preuve de taille polynomiale.NP=coNP

Joshua Grochow
la source
12

Si NP=PSPACE

1) Polynomial Hierarchy tomberait à .NP

2) Nous aurons maintenant que puisque nous savons que P S P A C EN LNPNLPSPACENL

---MISE À JOUR---

3) On sait que , où ce sont les versions bornées dans l'espace logarithmique de N P , C = P et P P respectivement. Puis , par définition , aucune de ces classes de complexité pourrait être égale N P en supposant que N P = P S P A C E .NLC=LPLNPC=PPPNPNP=PSPACE

Tayfun Pay
la source
1
Ce sont des conséquences triviales après PH PSPACE et NL PSPACE, j'espérais des conséquences plus surprenantes, par exemple quelque chose entre NL et P, ou toute nouvelle relation entre deux classes "strictement" en dessous de NP.
Denis
1
Notez que si vous considérez NL comme la classe de langues qui ont des solutions qui peuvent être vérifiées dans l'espace de journal, même si chaque symbole de la solution est lu au plus une fois (bien que de manière logarithmique, plusieurs puissent être stockés à tout moment sur la bande de travail) , le fait qu'il diffère de NP indique qu'il existe une classe L ' qui est un parent de L , impliquant des machines de Turing avec deux bandes d'entrée mais où l'une est en lecture seule et l'autre non, et qui est différente de P ( où parce qu'on a un espace polynomial sur la bande de travail, les limitations d'entrée en lecture seule n'ont pas d'importance).
Niel de Beaudrap
1
@dkuper Vous auriez aussi , où P L est l'espace logarithmique la version limitée de P P ainsi que # LN P , où # L est l'espace logarithmique la version limitée de # P . PLNPPLPP#LNP#L#P
Tayfun Pay
1
@dkuper voir math.ucdavis.edu/~greg/zoology/diagram.xml
Tayfun Pay
1
@TayfunPay: (1) pourquoi ne modifiez-vous pas votre réponse pour inclure les relations de votre commentaire? (2) Comment tiennent-ils?
Niel de Beaudrap le
10

En plus des résultats indiqués dans toutes les autres réponses, il y en a un impliquant les systèmes de preuve interactifs ( ), qui sont la généralisation N P où le vérificateur et le prouveur échangent des messages afin de reconnaître une langue.IPNP

IP=PSPACENP=PSPACE

Alex Grilo
la source
Cela pourrait quand même dépendre de la mise en œuvre? Cela signifie qu'il y aurait encore des prouveurs interactifs nécessitant plus d'échanges, seulement il en existe d'autres avec un seul message pour la même langue.
Denis
Eh bien, cela signifierait qu'un seul message est suffisant. Si j'ai bien compris votre question, il en va de même pour les problèmes de P: bien qu'il existe des algorithmes polynomiaux de temps pour eux, on peut toujours créer un algorithme de temps exponentiel.
Alex Grilo
2
@AlexGrilo: d'où mon commentaire sous la question :)
Alessandro Cosentino
@AlessandroCosentino Désolé, je ne l'ai pas vu avant
Alex Grilo