Jaka jest złożoność tej gry?

To jest uogólnienie mojego poprzedniego pytania .

Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle . Początkowo jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech 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 dolarów. Alice chce a Bob chce .$m_A$$m_B$$M^A(x)=1$$M^A(x)=0$

Na każdym etapie gry gracz może dodać jakiś ciąg do ; kosztuje to dolara, gdzie jest funkcją obliczaną w czasie wielomianowym. Również gracz może przegapić swój krok.$y$$A$$f(y)$$f: \{0,1\}^* \to \mathbb{N}$

Gra kończy się, jeśli obaj gracze wydadzą wszystkie pieniądze lub jeśli jakiś gracz opuści krok, gdy znajduje się na pozycji przegrywającej (co określa bieżąca wartość ).$M^A(x)$

Pytanie: jest problem zdefiniowania zwycięzcę tej grze za dany jest$M, f, x, m_A, m_B$

EXPSPACE - wykonać zadanie?

Zauważ, że może poprosić (za przynależność do ) 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 . Dlatego ten problem występuje w EXPSPACE . $M$$A$$A$

W moim poprzednim pytaniu dodanie każdego łańcucha do kosztuje jednego dolara (tj. ). Następnie (jak pokazał Lance Fortnow ) ta gra należy do EXPH, a nawet do PSPACE, jeśli . $A$$f \equiv 1$$m_A = m_B$

Powinno to być EXPSPACE-complete. Naszkicuję, jak osiągnąć wykładniczą liczbę alternatyw, bez ograniczania do tego problemu problemu z EXPSPACE, ale odtąd powinno to być łatwe do ukończenia.

Oznacz słowa w wyroczni po $t$ zaokrągleniu o $A_t$ , więc początkowo $A_0=\emptyset$ . Oznaczają słowa odpytywany przez $M^{A_t}$ przez $Q_t$ . Głównym obserwacja jest taka, że każdy, kto traci z $A_t$ , można założyć, aby dodać coś od $Q_t$ do $A$ . Jest tak, ponieważ w tej grze każdy ruch kosztuje pieniądze, chcemy się poruszać jak najmniej; nie ma sensu robić ruchu, dopóki nie wygramy. Ale oznacza to również, że jeśli tracimy, nie ma sensu dodawanie czegokolwiek spoza $Q_t$ .

Załóżmy dla uproszczenia, że $M$ działa dokładnie dla $2n$ kroków, a dla kroków $2i$ oraz $2i+1$ pyta słowo o długości dokładnie $i$ . Funkcja kosztu $f$ będzie po prostu $2^{-i}$ dla słów o długości $i$ . Gra będzie taki, że Alice zawsze musi dodać nieparzystej długości słowa i Bob zawsze musi dodać nawet długość słowa $A$ . Załóżmy, że $n$ jest dziwne i początkowo Alice traci.

Budżety $m_A$ i $m_B$ zostaną ustawione tak, że może ona wybrać dokładnie jeden o długości $n$ słów odpytywany przez $M^{A_0}$ do dodania do $A$ . Ta gra sprawi, że będzie ona zwycięzcą, więc Bob będzie musiał się ruszyć. Ponownie ze względu na ograniczenia budżetowe, będzie musiał wybrać dokładnie jeden o długości $n-1$ słowa na zapytania $M^{A_1}$ należy dodać do $A$ . Po dodaniu któregokolwiek z nich, $M^{A_2}$ wyśle ​​zapytanie o dwie nowe $n$ długości słów (te same, bez względu na to, jakie słowo Bob dodał do$A$ ), a Bob wygra. Alice będzie zmuszona dodać dokładnie jedno z tych nowychsłów odługości$n$ do$A$ aby wygrać.

Gra toczy się w ten sposób, co można sobie wyobrazić jako podążanie za gałęziami pełnego binarnego drzewa głębokości $n$ , chociaż w każdym rozgałęzionym węźle jeden z graczy (określony przez parzystość głębokości węzła) musi wykonać wybór o które to słowo, aby dodać do $A$ . Po przejściu przez drzewo skończy im się budżet. Jeśli na którymś etapie gry jedno z nich zdecyduje się dodać jakieś słowo, które jest krótsze (np. Alicja o długości $k<n$ słowa z $Q_0$w pierwszym kroku), a jeśli inny gracz (w naszym przykładzie Bob) po prostu zagra zawsze najdłuższe słowo w drzewie binarnym, na końcu pozostanie mu trochę pieniędzy, a my stworzymy grę, aby mógł z tego skorzystać wygrać. (Pamiętaj, że Alice może również mieć trochę pieniędzy, ale Bob będzie miał więcej, więc projektujemy grę końcową, aby jeśli jeden z nich miał więcej pieniędzy, wtedy ten gracz może wygrać.)

W ten sposób Alice decyduje się na wykładniczo wiele par słów o nieparzystej długości, a Bob o wykładniczo wiele słów o parzystej długości, które jedna z każdej pary idzie do $A$ , i dokonują tych wyborów na przemian.