Le temps est-il quasi-polynomial dans PSPACE?

14

J'avais fait quelques recherches à ce sujet mais je n'ai pas pu trouver de réponse dans les deux cas.

Huck y répondit pleinement. Merci :)

Tayfun Pay
la source
1
Pouvez-vous déplacer votre "commentaire dans la question" vers un commentaire réel.
Suresh Venkat
@Suresh, je ne pense pas qu'il y ait assez de place pour ça? Je ne suis pas sûr.
Tayfun Payez
2
Pouvez-vous peut-être supprimer entièrement la partie "commentaire"? Je ne pense pas que ce soit approprié.
Jukka Suomela,
1
Mettez tout ce que vous pouvez et retirez le reste. Et postez ceci dans la réponse de Huck. Il n'est pas approprié d'insérer un commentaire de réponse dans la question d'origine
Suresh Venkat

Réponses:

27

Voici un argument simple qui montre que QP n'est pas connu pour être dans PSPACE:

Supposons . Nous avons alors P Q P P S P A C E , où la première inclusion est propre au théorème de la hiérarchie temporelle.QPPSPUNECEPQPPSPUNECE

Cela sépare de P S P A C E , qui n'est pas connu pour être maintenu, donc Q P P S P A C E ne doit pas non plus être connu pour être maintenu.PPSPUNECEQPPSPUNECE

En effet, nous avons que , mais Q P P S P A C E ne sépare pas les deux classes par le THT (comme indiqué dans la question ).PSPUNECEQPPSPUNECEEXPQPPSPUNECE

Huck Bennett
la source