Rozważ następującą grę na ukierunkowanym wykresie ważonym z chipem w pewnym węźle.
Wszystkie węzły oznaczone są literą A lub B.
Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B).
Początkowo Alice i Bob mają odpowiednio i dolarów.
Jeśli gracz znajduje się na pozycji przegrywającej (tzn. Bieżąca pozycja żetonu jest oznaczona przeciwną literą), może on przenieść żeton do sąsiedniego węzła. Taki ruch kosztuje kilka dolarów (waga odpowiedniej krawędzi).
Gracz przegrywa, jeśli znajduje się na przegranej pozycji i nie ma pieniędzy, aby to naprawić.
Rozważmy teraz GRA językowa, która składa się ze wszystkich ukierunkowanych ważonych wykresów (wszystkie wagi są dodatnimi liczbami całkowitymi), początkowej pozycji układu oraz literami Alicji i Boba, które są podane w jednostkowej reprezentacji
tak, że Alice ma zwycięską strategię w tej grze.
GAME język należący do P . Rzeczywiście, obecna pozycja gry jest określona przez pozycję chipa i bieżące stolice Alicji i Boba, więc programowanie dynamiczne działa (tutaj ważne jest, aby początkowe kapitały były podawane w postaci jednoargumentowej).
Teraz rozważ następujące uogólnienie tej gry. Rozważyć kilka skierowanych ważone wykresy w układ na każdym wykresie. Wszystkie węzły wszystkich wykresów są oznaczone A i B. Teraz Bob wygrywa, jeśli wszystkie żetony są oznaczone B, a Alice wygrywa, jeśli co najmniej jeden żeton jest oznaczony A.
Rozważmy wielu języków grze, który składa się ze wszystkich wykresach początkowe położenie i literami i (w jednoargumentowy reprezentacji) tak, Alicja wygrywa odpowiedniego gry. Ważne jest, aby wielkie litery były wspólne dla wszystkich grafów, więc nie jest to tylko kilka niezależnych GRA.
Pytanie Jaka jest złożoność języka MULTI-GAMES? (Czy to też należy do P, czy jest jakiś powód, aby sądzić, że ten problem jest trudny?)
UPD1 Neal Young zaproponował wykorzystanie teorii Conwaya. Nie wiem jednak, czy można zastosować tę teorię do kilku gier ze wspólnym kapitałem.
UPD2 Chcę pokazać przykład, który pokazuje, że MULTI-GAME nie jest bardzo prosta. Niech Alice podzieli swój kapitał na niektóre składników (Ona ma zamiar użyć dolary dla -tej wykresie). Zdefiniuj jako minimalnej liczby taki, że w -ty gry Bob wygrywa, jeśli Alicja i Bob mają ja i b i dolarów odpowiednio. Jeśli b 1 + … b (dla niektórych podziałów ) wtedy Alice wygrywa. Jednak przeciwieństwo nie jest prawdą. Rozważ dwie kopie poniższego wykresu (początkowo układ znajduje się po lewej stronie A):
Dla jednego wykresu wygrywa Bob, jeśli i lub jeśli i . Jednak w grze z dwiema kopiami tego wykresu Bob przegrywa, jeśli i . Rzeczywiście, Bob musiał spędzić lub dolarów, aby przesunąć oba chipy do węzła naznaczonym . Następnie Alice może przenieść co najmniej jeden żeton do węzła oznaczonego literą A. Po tym Bob nie ma pieniędzy, aby zapisać swoją pozycję.
UPD3 Ponieważ pytanie o dowolne wykresy wydaje się trudne, rozważ konkretne wykresy. Oznacz węzły niektórych wykresów jako . Moje ograniczenie jest następujące: dla każdej pary istnieje krawędź od do i nie ma odwrotnej krawędzi. Istnieje również ograniczenie kosztów krawędzi: dla krawędź do nie jest większa niż od do .
źródło
Odpowiedzi:
Ponieważ odpowiedź Stevena Stadnickiego nie wydaje się być zaakceptowana przez pytającego, doszedłem do wniosku, że nadal przydatne może być dostarczenie aktualizacji: mam redukcję z 3SAT do MULTI-GAME. Nie przyjrzałem się uważnie odpowiedzi Stevena ani nie podążyłem za linkiem, który podał, ale na podstawie poniższej redukcji nie zdziwię się, jeśli MULTI-GAME jest rzeczywiście ukończony na PSPACE. Jednak nie zawracam sobie głowy przedłużeniem tego wyniku poza twardość NP.
Instancja 3SAT składa się z klauzulC1,…,Cm , przy czym każda klauzula ma postać Ci=Li1∨Li2∨Li3 gdzie każda Lik jest jedną ze zmiennych x1,…,xn lub negacja jednej ze zmiennych.
Biorąc pod uwagę taką instancję 3SAT, redukcja tworzy instancję MULTI-GAME składającą się zn+1 gier - jednej dla każdej zmiennej i innej gry wykorzystywanej jako ujście nadwyżki kapitału. Najpierw zdefiniujemy strukturę wykresów dla każdej gry, następnie popatrzymy na przykład i omówimy podstawową ideę, a następnie ustalimy, jakie dokładne koszty przypisać do krawędzi, aby utrzymać mocne ograniczenie.
Po pierwsze, zmienny wykres gryGj dla każdej zmiennej xj :
Dla każdego literałuLik klauzuli Ci , jeśli Lik=xj lub Lik=¬xj , utwórz wierzchołki oznaczone CiTA i CiFA oznaczone A i wierzchołki oznaczone CiTB i CiFB oznaczone B. Dodaj krawędzie (T,CiTA) i(F,CiFA) z kosztami ustawionymi nalik . (Będziemy określićlik później).
Dodaj krawędzie(CiTA,CiTB) i (CiTA,CiTB) . Jeśli Lik=xj , to ustaw (CiTA,CiTB) na lik−1 i( C i TA, C i T B ) na l i k . W innym przypadku ( C i(CiTA,CiTB) lik (CiTA,CiTB) koszt T A , C i T B ) nalik orazkoszt(CiTA,CiTB) nalik−1 .
Gra w zlew kapitału:
Jest to wiele do zrobienia, więc mam nadzieję, że przykład sprawi, że będzie to trochę łatwiejsze do strawienia. Nasza instancja 3SAT wygląda następująco:
Redukcja zamienia to wystąpienie w 4 zmienne wykresy gier i 1 wykres ujścia kapitału. Na poniższych schematach czerwone wierzchołki są oznaczone literą A (tj. Wygrywające pozycje dla Alicji), a cyjanowe wierzchołki są oznaczone literą B (wygrywające pozycje dla Boba).
Wykres dlax1 :
Wykres dlax2 :
Wykres dla ujścia kapitału:
Pomysł jest następujący:
Bob jest zmuszony zrobić pierwszyn n
Alice będzie miała wystarczającą ilość kapitału, aby wykonać dokładnie 4 ruchy, z których każdy będzie musiał mieć wystarczającą ilość kapitału, aby mógł wygrać. Wartościci a lik Ci
Jeśli otwarcie Boba spełnia wszystkie klauzule, możemy argumentować ograniczenia opcji Alice, które wykluczają jakąkolwiek inną możliwość wygranej Alice. Zauważ, że kolejność, w jakiej Alice wykonuje swoje ruchy, jest nieistotna, ponieważ odpowiedzi Boba są wymuszone, a całkowity kapitał, którego będzie potrzebował Bob, aby zareagować na ruchy Alice, nie jest zmieniany przez kolejność ruchów Alice.
Uwaga do mojej poprzedniej odpowiedzi: z perspektywy czasu jest oczywiste, że dla wariantu MULTI-GAME TABELA zdefiniowanego w komentarzach do tej odpowiedzi, DP w stylu plecaka wystarcza, aby ustalić, który gracz ma strategię wygrywającą. Możesz argumentować, że najlepszą strategią Boba jest zawsze reagowanie na przegrany stan przy danym stole gry przy minimalnej możliwej inwestycji (nie może to odciąć kolejnego ruchu dla Boba, który miałby w przeciwnym razie), a stamtąd zamówienie ruchów Alice nie ma znaczenia. Następnie staje się kwestią wyboru podziału kapitału Alicji między gry, tak aby suma minimalnych wygranych odpowiedzi Boba w stosunku do tych gier przekroczyła jego budżet, który można zmienić jako problem typu plecakowego, który ma DP w czasie wielomianowym do jednolitej reprezentacji kosztów. (Moje ponowne wystąpienie faktycznie „
Nie myślałem dużo o twoim specjalnym przypadku z UPD3 . Podejrzewam, że jest to trudne NP, z tego powodu, że moje zmienne gadżety wydają się na pierwszy rzut oka, jakby można je było dostosować do tych ograniczeń, ale prawdopodobnie nie przyjrzę się temu dalej.
źródło
Aktualizacja: prawdopodobnie niepoprawna, na razie pozostawiająca jako dowód na zbadanie alei. Zobacz komentarze.
Aktualizacja 2: zdecydowanie niepoprawna.
Wstępnie obliczone
i
źródło
źródło