Ce jeu EXPSPACE est-il complet?

Que soit une machine déterministe polynomial qui peut poser des questions à un oracle A . Initialement, A est vide mais cela peut être modifié après un jeu qui sera décrit ci-dessous. Soit x une chaîne.$M$$A$$A$$x$

Considérez le jeu Alice et Bob suivant. Initialement, Alice et Bob ont respectivement et m B dollars. Alice veut M A ( x ) = 1 et Bob veut M A ( x ) = 0 .$m_A$$m_B$$M^A(x)=1$$M^A(x)=0$

À chaque étape du jeu, un joueur peut ajouter une chaîne à ; cela coûte un dollar. Un joueur peut également manquer son pas.$A$

Le jeu se termine si les deux joueurs dépensent tout leur argent ou si un joueur a raté un pas alors qu'il ou elle est en position perdante (cela se définit par la valeur actuelle de ).$M^A(x)$

Question: est le problème de définir le gagnant de ce jeu pour donné , x , m A , m B est un$M, x, m_A, m_B$

EXPSPACE - tâche complète?

Notez que peut demander (pour appartenance à A ) que les chaînes de longueur polynomiale donc il n'y a pas de sens pour Alice ou Bob à ajouter des chaînes plus plus à A . Par conséquent, ce problème se trouve dans EXPSPACE . $M$$A$$A$

Je n'ai pas de caractérisation exacte, mais il est peu probable que ce problème soit complet pour EXPSPACE. Supposons que $M^{\Sigma^*}(x)$$S$$S$$m_A$