Czy ta gra jest EXPSPACE?

Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle A . Początkowo A jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech x będzie ciągiem znaków.$M$$A$$A$$x$

Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio i m B dolarów. Alicja chce M A ( x ) = 1, a Bob chce M A ( x ) = 0 .$m_A$$m_B$$M^A(x)=1$$M^A(x)=0$

Na każdym etapie gry gracz może dodać jeden ciąg do ; kosztuje to jednego dolara. Również gracz może przegapić swój krok.$A$

Końce grać, jeśli obu graczy spędza wszystkie pieniądze lub jeśli jakiś gracz brakowało krok, gdy on lub ona w przegranej pozycji (definiująca według bieżącej wartości ).$M^A(x)$

Pytanie: czy problemem jest określenie zwycięzcy tej gry dla danego to$M, x, m_A, m_B$

EXPSPACE - wykonać zadanie?

Zauważ, że może poprosić (za przynależność do A ) tylko ciągi długości wielomianu, więc nie ma sensu dla Alice lub Bob dodać więcej dłuższe ciągi do A . Dlatego ten problem występuje w EXPSPACE . $M$$A$$A$

$M^{\Sigma^*}(x)$$S$$S$$m_A$