Was ist die Komplexität dieses Spiels?

10

Dies ist eine Verallgemeinerung meiner vorherigen Frage .

Sei M 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.

Betrachten Sie das folgende Spiel von Alice und Bob. Anfangs haben Alice und Bob mA bzw. mB Dollar. Alice will MA(x)=1 und Bob will MA(x)=0 .

Bei jedem Schritt des Spiels ein Spieler eine Zeichenfolge hinzufügen y zu A ; Diese Kosten f(y) Dollar, wobei f:{0,1}N ist eine Polynom-berechenbare Funktion. Auch ein Spieler kann seinen Schritt verpassen.

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 M,f,x,mA,mB ist ein

EXPSPACE - Aufgabe abschließen?

Beachten Sie, dass M (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 .

In meiner vorherigen Frage kostet das Hinzufügen jeder Zeichenfolge zu A einen Dollar (dh f1 ). Dann ist (wie es durch gezeigt wurde Lance Fortnow dieses Spiel) gehört zu EXPH und sogar zu PSPACE wenn mA=mB .

Alexey Milovanov
quelle
Können Sie erklären, warum Sie diese Änderung am Problem vorgenommen haben? Alice kann überprüfen, ob sie es sich leisten kann, alle Zeichenfolgen in (wie in Lances Antwort auf Ihr anderes Problem definiert) in Polynomzeit zu bezahlen . Wie löst dies das Problem nicht sofort? S
Stella Biderman
@StellaBiderman Alice kann dies tatsächlich in Polynomzeit überprüfen. Wenn sie jedoch nicht genug Geld hat, bedeutet dies nicht, dass sie nur polynomielle Schritte ausführen kann (wie im vorherigen Spiel).
Alexey Milovanov
Wenn sie sich nicht leisten kann, kann sie jemals einen Gegner schlagen, der immer an der Reihe ist? Vielleicht gibt es etwas an der Spieleinstellung, das ich nicht verstehe. S
Stella Biderman
1
@Stella Ja, weil es sich möglicherweise um andere akzeptierende Pfade handelt. Nehmen wir zum Beispiel an, wenn , dann stoppt M und akzeptiert. In diesem Fall ist S = { x 1 } . Aber wenn x 1A ist , könnte M x 2 abfragen und akzeptieren, wenn x 2A ist . In diesem Fall reicht es aus, wenn Alice genug Spondulix für x 2 hat . x1AMS={x1}x1AMx2x2Ax2
Domotorp

Antworten:

5

Dies sollte EXPSPACE-vollständig sein. Ich werde skizzieren, wie eine exponentielle Anzahl von Alternativen erreicht werden kann, ohne ein EXPSPACE-vollständiges Problem auf dieses zu reduzieren, aber von hier aus sollte es einfach zu beenden sein.

tAtA0=MAtQtAtQtAQt

M2n2i2i+1if2iiAn

mAmBnMA0An1MA1AMA2nAnA

nAk<nQ0im ersten Schritt), wenn der andere Spieler (in unserem Beispiel Bob) immer nur das längste Wort spielt, das er im Binärbaum kann, hat er am Ende noch etwas Geld übrig und wir machen das Spiel, damit er es verwenden kann gewinnen. (Beachten Sie, dass Alice möglicherweise auch noch etwas Geld übrig hat, Bob jedoch mehr. Daher gestalten wir das Endspiel so, dass dieser Spieler gewinnen kann, wenn einer von ihnen mehr Geld hat.)

A

domotorp
quelle
Vielen Dank für Ihre Antwort. Ich habe Ihnen einige Fragen per E-Mail gestellt.
Alexey Milovanov