Deje que sea una máquina determinista en tiempo polinómico que pueden hacer preguntas a algún oráculo A . Inicialmente, A está vacío, pero esto se puede cambiar después de un juego que se describirá a continuación. Deje x ser una cadena.
Considere el siguiente juego de Alice y Bob. Inicialmente, Alice y Bob tienen y m B dólares respectivamente. Alice quiere M A ( x ) = 1 y Bob quiere M A ( x ) = 0 .
En cada paso del juego, un jugador puede agregar una cadena a ; Esto cuesta un dólar. También un jugador puede perder su paso.
La jugada finaliza si ambos jugadores gastan todo el dinero o si algún jugador perdió el paso cuando estaba en una posición perdedora (eso se define por el valor actual de ).
Pregunta: ¿el problema de definir al ganador de este juego para es un
EXPSPACE -tarea completa?
Tenga en cuenta que puede pedir (por pertenecer a una ) sólo cadenas de longitud polinómica lo que no hay sentido para Alice o Bob para añadir cadenas más largas a una . Por lo tanto, este problema está en EXPSPACE .
fuente