Problèmes non connus pour être PSPACE-complete

12

Quels sont les problèmes avec les propriétés suivantes:

1) ils sont la restriction de problèmes (peut-être bien connus) qui sont PSPACE-complets;

2) les versions restreintes sont dans PSPACE, mais c'est un problème ouvert si elles sont complètes pour PSPACE (ou même si elles sont NP-hard).

Quatre exemples de "puzzles & C.":

La complexité de 1x1 Rush Hour [1] (PSPACE-complete pour les blocs de taille 2x1);
[ RESOLU ] La complexité du plan de métro Subway Shuffle [1] (PSPACE-complet même pour les graphiques planaires, un brouillon du document peut être téléchargé ici );
La complexité de Lunar-Lockout sans blocs fixes [1] (PSPACE-complete avec blocs fixes);
(pas si célèbre) La complexité de (mon) problème de réseau de commutation (c'est une restriction du Sokoban complet de PSPACE, NP-dur dans le cas non planaire, voir ce Q&R sur cstheory ).

Si vous en avez plusieurs, regroupez-les par sujet.

[1] Robert A. Hearn, Erik D. Demaine: jeux, puzzles et calcul. AK Peters 2009, ISBN 978-1-56881-322-6, pp. I-IX, 1-237

big-list open-problem Marzio De Biasi
la source

1

Presque tous les problèmes complets de PSPACE ont de nombreux cas particuliers que personne n'a pris la peine d'étudier. Comment définissez-vous le problème ouvert ?

RB

@RB: "problème ouvert" un problème qui est actuellement à l'étude (ou qui a été étudié, cité plusieurs fois, ...) et les chercheurs pensent qu'il serait intéressant de le résoudre (au moins pour façonner la frontière des problèmes PSPACE-complete ... à l'ombre du démon P vs PSPACE :-).

Marzio De Biasi

1

TAUT est une version restreinte de QBF, et c'est un problème ouvert, qu'il soit PSPACE ou NP-dur, donc il répond à toutes les exigences, mais je ne pense pas que ce soit dans le bon esprit.

Emil Jeřábek

@ EmilJeřábek: QBF limité à un nombre fini de quantificateurs pourrait être dans l'esprit (c'est-à-dire PH vs PSPACE) ... mais c'est un saut de "infini à fini"; Je suis plus intéressé par les restrictions sur les "structures" finies du problème.

Marzio De Biasi

12

Échecs rétrogrades. Il est complet sur si vous êtes autorisé à avoir arbitrairement plusieurs rois et qu'aucun d'entre eux ne peut être en échec à tout moment. Si aucun (ou un seul par joueur) rois n'est autorisé, il est connu qu'il y a des positions qui nécessitent des mouvements exponentiels, mais le problème n'est connu que pour être dur. $PSPACE$ $NP$

http://arxiv.org/abs/1409.1530

/mathpro/27944/do-there-exist-chess-positions-that-require-exponential-many-moves-to-reach

Tom van der Zanden
la source

11

Je ne sais pas si cela correspond à votre notion de restriction, mais voilà.

Le "problème de taille de circuit minimum QBF-oracle": étant donné la table de vérité d'une fonction booléenne et du paramètre k, existe-t-il un circuit de taille au plus k calculant la fonction sur la base ET, OU, NON, et QBF? (Une porte QBF interprète sa chaîne d'entrée comme une formule booléenne F entièrement quantifiée, et la sortie est 1 si F est vrai.)

Le problème est certainement dans PSPACE, connu pour être complet sous les réductions de ZPP, mais pas connu pour les réductions de temps polynomiales déterministes. Il est possible que PSPACE ne soit pas complet dans le cadre des réductions d'espace de journalisation! Voir Allender, Holden et Kabanets .

Ryan Williams
la source

(Pas lié à cette réponse, mais de toute façon,) Comment savons-nous que le problème de l' ensemble à 7 dominants sur les graphes à n nœuds peut être résolu en "n temps? Référence 17 ne fait que cette revendication pour ≥ 8.

^{7 + o (1)}

$^{7+o(1)}$

ℓ

$\ell$

(J'aurais dû le mentionner plus tôt, mais) J'ai maintenant une question sur le cas k = 7 sur ce site.

5

Le problème suivant correspond à l'exigence en quelque sorte double ...

Confinement d'expressions régulières , c'est-à-dire tester si le langage d'une expression régulière est contenu dans le langage d'une expression régulière (c'est-à-dire si ) est un PSPACE bien connu -problème complet, même si est choisi comme (alors on l'appelle Universalité des expressions régulières). $r$ $r'$ $L(r)\subseteq L(r')$ $r$ $\Sigma^*$

De même, l' équivalence des expressions régulières demande si et est PSPACE-complet (dureté résultant de l' universalité ). $L(r)=L(r')$

Cependant, l'image devient moins claire pour les expressions régulières de chaîne : elles sont de la forme générale (donc: chaîne) avec seulement des facteurs restreints . Un facteur peut être de la forme où chaque est une chaîne ou ou ouavec le même type de . Un exemple est. $r_1\cdots r_n$ $r_i$ $e=(w_1+\ldots+w_m)$ $w_j$ $e^*$ $e^+$ $e?$ $e$ $a(b+cd)(ab+cde+f)^*d?$

Le confinement des expressions régulières de la chaîne est toujours complet sur PSPACE mais l' équivalence des expressions régulières de la chaîne n'est pas claire (bien que connu pour être coNP-hard et dans PSPACE).

Soit dit en passant, la limite supérieure de PSPACE suit facilement en traduisant les expressions en NFA et en recherchant de manière non déterministe un contre-exemple: devinez une chaîne lettre par lettre et gardez une trace des jeux d'états qui peuvent être atteints dans les NFA.

Thomas S
la source

2

jeux avec seulement 2 boutons et 2 portes dans lesquels toutes les portes sont initialement fermées:

Les "niveaux" sont des sous-graphes finis de la grille planaire . sommets sont identifiés comme l'un des [début, bouton, vide, porte, fin]. Chaque sommet de porte possède un ensemble de boutons d'ouverture et un ensemble de boutons de fermeture. Une k-porte est une porte qui est contrôlée par au plus k boutons, et un k-bouton est un bouton qui contrôle au plus k portes. Chaque fois que sur un sommet de bouton, on peut appuyer sur le bouton, ce qui ouvre les portes pour lesquelles le bouton est un bouton d'ouverture et ferme les portes pour lesquelles le bouton est un bouton de fermeture. Le but est de passer du sommet de départ au sommet de fin sans passer par des portes fermées. $\:$ $\:$ $\:$ $\:$ $\:$

Ces niveaux peuvent clairement être résolus dans FPSPACE, et les résoudre est difficile FNPSPACE
même lorsque [chaque porte a exactement un bouton d'ouverture et exactement un bouton de fermeture]
et [chaque bouton ouvre exactement une porte et ferme exactement une porte].
D'un autre côté, cet article déclare que "C'est un problème ouvert de savoir si un jeu avec
2 boutons et 2 portes reste PSPACE-hard lorsque toutes les portes sont initialement fermées."

La dureté FNPSPACE lorsque toutes les portes sont initialement fermées sera récupérée si les conditions exactement une de chaque de mon paragraphe précédent sont modifiées de l'une des manières suivantes:

permettre aux portes d'avoir 2 boutons d'ouverture (en plus d'1 bouton de fermeture)
ou
permettre aux boutons de fermer 2 portes (en plus d'ouvrir 1 porte)

.

La page 10 de ce document montre que la détermination de la solvabilité est NC1 -hard même sans boutons et
sans portes. Sinon, je ne connais aucun résultat de dureté pour résoudre les niveaux avec 2 boutons et 2 portes lorsque toutes les portes sont initialement fermées (même sans les conditions exactes d'une de chaque). $\:$

la source

Avez-vous une preuve ou une référence simple pour la dureté de la version à signe opposé (où chaque bouton ouvre une porte et en ferme une autre, et chaque porte est ouverte par un bouton et fermée par un autre)?

Jonas Kölker

Non, même si je me rends compte que je sais montrer la dureté même lorsque toutes les portes commencent fermées, ce que je publierai probablement cette année.

Je pense que j'ai aussi une idée de comment le faire. Souhaitez-vous m'envoyer une copie de votre manuscrit lorsque vous le ferez accepter? J'adorerais comparer des idées :-) [re: la dureté opposée au signe, IINM la réduction dans le papier Bloxorz est opposée au signe sur les portes et les boutons.]

Jonas Kölker

Oui.

Problèmes non connus pour être PSPACE-complete

Réponses: