Czy istnieje prosta gra o asymetrycznej złożoności?

Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch wygrywającym, jeśli pozycja nadal wygrywa po rozegraniu go.) Aby rozróżnić, wywołam dawną KOMPLEKSOWOŚĆ POZYCJI, a drugą MOKĄ KOMPLEKSOWOŚĆ.

Łatwo zauważyć, że jeśli MOVE-COMPLEXITY jest w lub , to i POZYCJA-COMPLEXITY - możemy obliczyć optymalne ruchy i sprawdzić, kto wygra na końcu. (Naprawdę nie zastanawiałem się, co się stanie, jeśli MOVE-COMPLEXITY jest w , prawdopodobnie POSITION-COMPLEXITY jest w czymś w rodzaju ). Istnieją jednak fikcyjne przykłady, gdy MOVE-COMPLEXITY jest trywialny, a POZYCJA -WSPÓŁPRACA jest arbitralnie trudna - podobnie jak (niezbyt interesująca) gra polegająca na sprawdzaniu wyniku działania algorytmu, w której gracze wykonują kolejne kroki, mając tylko jeden ruch. Trochę dygresowałem, moje główne pytanie jest następujące.P S P A C E N P P N $P$$PSPACE$$NP$$P^{NP}$

Czy istnieje naturalna gra, w której MOVE-COMPLEXITY dwóch graczy jest inna?

Na przykład gra, w której pierwszy gracz wybiera wartości zmiennych CNF (która może nie mieć rozwiązania), podczas gdy drugi gracz próbuje rozwiązać zagadkę SOKO-BAN (która może nie mieć rozwiązania), jest taki przykład.

Być może dość naturalna gra to:

Gracz 1 jest umieszczony w środku labiryntu i musi dotrzeć do wyjścia, aby wygrać.

Gracz 2 znajduje się w tym samym labiryncie i musi zebrać zestaw „komponentów”, aby zbudować kontroler radiowy, który pozwoli mu zamknąć wyjście (i wygrać).

Decyzja o kolejnym ruchu ze zwycięskiej pozycji jest łatwa dla Gracza 1: wystarczy podążać najkrótszą ścieżką od jego aktualnej pozycji i wyjścia; ale może to być bardzo trudne dla Gracza 2.
Rzeczywiście, jeśli (pozostałe) komponenty kontrolera radiowego znajdują się na wierzchołkach wykresu siatki węzłów (załóżmy, że Gracz 2 jest sam na sąsiednim wierzchołku) i odległość między Graczem 1 a wyjście jest dokładnie , a następnie musi znaleźć ścieżkę hamiltonowską, aby się ruszyć.$n$$n$

Aby uczynić grę bardziej „interaktywną”, możemy również dodać kilka dodatkowych akcji do Gracza 2, które mogą spowodować jedynie spowolnienie wielomianowe w obliczeniach następnego ruchu dla Gracza 1; na przykład pozwalając mu blokować stałą liczbę korytarzy labiryntu.

Dzięki twoim ograniczeniom mamy również silniejszą zależność odwrotną: jeśli POZYCJA-KOMPLEKSOWOŚĆ należy do klasy , to i tak MOŻLIWOŚĆ KOMPLEKSOWA, ponieważ wystarczy przetestować skończoną liczbę dostępnych ruchów. (Zakładałem, że „skończony” miałeś na myśli „stały”, jeśli jest arbitralny, wówczas złożoność może się zmienić).$C$

Wystarczy spojrzeć na niektóre naturalne gry, w których POZYCJA-KOMPLEKSOWOŚĆ jest asymetryczna. Zawsze będziemy potrzebować pewnej asymetrii między graczami, aby stworzyć takie sytuacje, ale mam nadzieję, że będzie to jak najbardziej naturalne.

Moim zdaniem gry z częściową obserwacją są tego dobrym przykładem: rozgrywane są na skończonej arenie, a jeden gracz zawsze zna aktualny wierzchołek, podczas gdy drugi tylko wie, w której grupie jest obecny wierzchołek (są one arbitralnie grupowane razem). Najbardziej klasycznym przykładem tego są gry z parzystością, w których liczba ruchów jest nieskończona. Tam złożoność POZYCJI jest kompletna WYŁĄCZNIE dla częściowego gracza w porównaniu do liniowego / kwadratowego / NP coNP dla pełnego gracza, w zależności od złożoności warunków wygranej. Zobacz tutaj odniesienie na ten temat.$\cap$

Myślę, że z tego możemy zaprojektować grę rozgrywaną w skończonym czasie, w której jeden gracz ma częściową obserwację, a drugi pełną obserwację, a złożoność POZYCJA i złożoność RUCHU są bardzo różne. Naturalną próbą jest podzielenie wierzchołków na i i ustawienie warunku wygranej na „zagraj ruchy , Gracz wygrywa, jeśli zakończymy partycję ”.P 2 p ( n ) i P $P_1$$P_2$$p(n)$$i$$P_i$

W rzeczywistości w tak zwanych grach Picker-Chooser lub Chooser-Picker łatwo jest skonstruować przykłady, dla których najlepszą strategią jednego gracza jest prosta strategia parowania, podczas gdy drugi musi rozwiązać 3-SAT na dowolnym określonym wcześniej CNF, to jest problem NP-zupełny.

Powiedzmy, że gry Picker-Chooser to gra asymetryczna na hiperrafacie H = (V, E): Picker wybiera dwa niezaznaczone elementy V, a następnie Selectr bierze jeden z nich i zwraca drugi do Picker. Wybieracz wygrywa, jeśli otrzymuje wszystkie elementy litery A od E. Teraz, biorąc pod uwagę formułę CNF F od 3-SAT, V jest zbiorem literałów, a E realizuje jakiś gadżet. Podsumowując, Picker musi zawsze oferować x_i i x_i negację na wszystkich etapach (w przeciwnym razie natychmiast traci), podczas gdy wybór selektora jest dowolnym wejściem 0-1 dla dowolnego x_i, a on wygrywa, spełniając F.

Zobacz szczegóły w: A. Csernenszky, R. Martin i A. Pluhár, O złożoności gier pozycyjnych selektor-zbieracz. Liczby całkowite 11 (2011).

lub na stronie : http://www.inf.u-szeged.hu/~pluhar/complexity_2011.pdf