Ist dieses Spiel EXPSPACE-vollständig?

10

Sei eine polynomialzeitdeterministische Maschine, die einem Orakel A Fragen stellen kann . Anfangs ist A leer, aber dies kann nach einem Spiel geändert werden, das unten beschrieben wird. Sei x eine Zeichenfolge.MAAx

Betrachten Sie das folgende Spiel von Alice und Bob. Anfangs haben Alice und Bob bzw. m B Dollar. Alice will M A ( x ) = 1 und Bob will M A ( x ) = 0 .mAmBMA(x)=1MA(x)=0

Bei jedem Schritt des Spiels kann ein Spieler eine Saite hinzufügen . Das kostet einen Dollar. Auch ein Spieler kann seinen Schritt verpassen.A

Das Spiel endet , wenn beide Spieler verbringt alles Geld oder wenn einige Spieler Schritt , wenn er oder sie in einer Verlustposition (dh definiert durch den aktuellen Wert der verpassten ).MA(x)

Frage: Ist das Problem der Definition des Gewinners dieses Spiels für gegebenes ist einM,x,mA,mB

EXPSPACE - Aufgabe abschließen?

Beachten Sie, dass (für die Zugehörigkeit zu A ) nur Zeichenfolgen mit Polynomlänge anfordern kann, sodass Alice oder Bob keinen Sinn haben, A längere Zeichenfolgen hinzuzufügen . Daher liegt dieses Problem in EXPSPACE . MAA

Alexey Milovanov
quelle

Antworten:

7

MΣ(x)SSmA

Lance Fortnow
quelle