¿Es este juego EXPSPACE-complete?

10

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.MAAx

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 .mAmBMA(x)=1MA(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.A

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 ).MA(x)

Pregunta: ¿el problema de definir al ganador de este juego para es unM,x,mA,mB

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 . MAA

Alexey Milovanov
fuente

Respuestas:

7

MΣ(x)SSmA

Lance Fortnow
fuente