Esta es una generalización de mi pregunta anterior .
Deje que sea una máquina determinista en tiempo polinómico que pueden hacer preguntas a algún oráculo . Inicialmente, está vacío, pero esto se puede cambiar después de un juego que se describirá a continuación. Deje ser una cadena.
Considere el siguiente juego de Alice y Bob. Inicialmente, Alice y Bob tienen y dólares respectivamente. Alice quiere y Bob quiere .
En cada paso del juego, un jugador puede agregar un poco de cuerda a ; esto cuesta dólar, donde es una función computable de tiempo polinomial. 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 ) sólo cadenas de longitud polinómica lo que no hay sentido para Alice o Bob para añadir cadenas más largas a . Por lo tanto, este problema está en EXPSPACE .
fuente
Respuestas:
Esto debería ser EXPSPACE-complete. Dibujaré cómo lograr un número exponencial de alternancias, sin reducir ningún problema de EXPSPACE-complete a este, pero desde aquí debería ser simple terminar.
fuente