Referencyjne gry z niepowiązanymi półprywatnymi monetami

Byłem (i nadal jestem) bardzo zainteresowany odpowiedzią na to pytanie, ponieważ jest to interesująca odmiana złożoności gier, która nie została jeszcze rozwiązana, więc zaoferowałem nagrodę. Pomyślałem, że pierwotne pytanie jest prawdopodobnie zbyt trudne, więc zamieściłem trzy powiązane pytania, które również byłyby warte nagrody. Nikt nie opublikował żadnych odpowiedzi przed wygaśnięciem nagrody. Później mogłem odpowiedzieć na dwa powiązane pytania (pytania 3 i 4, omówione poniżej mojego oryginalnego postu), pokazując, że przybliżenie wartości gier, do których się odwołujemy, za pomocą skorelowanych półprywatnych monet (zdefiniowanych poniżej) było zakończone WYŁĄCZNIE. Pierwotne pytanie wciąż pozostaje bez odpowiedzi. Byłbym również zainteresowany wszelkimi wynikami umieszczającymi powiązane gry między PSPACE i EXPTIME w interesujących klasach złożoności.

ORYGINALNY POCZTA:

To pytanie zostało zainspirowane dyskusją na temat pytania heksowego Itai . Gra sędziował to gra, w której dwie obliczeniowo nieograniczone gracze komunikując się za pomocą wielomianu czasie weryfikator, który może odwrócić prywatne monety (stąd liczba zwojów, a kwota komunikacji jest również ograniczony czas wielomianowy). Na koniec gry sędzia uruchamia algorytm w P, aby ustalić, kto wygra. Ustalenie, kto wygra taką grę (nawet w przybliżeniu), kończy się WYPŁATĄ. Jeśli masz publiczne monety i komunikację publiczną, takie gry są w PSPACE. ( Zobacz Feige i Killian, „Making Games Short.” ) Moje pytanie dotyczy granicy między tymi dwoma wynikami.

• Pytanie: Załóżmy, że masz dwóch graczy bez ograniczeń obliczeniowych, którzy grają w grę o wielomianach. Rola sędziego jest ograniczona do tego, aby przed każdym ruchem dać każdemu graczowi pewną liczbę prywatnych rzutów monetą (nieskorelowanych z innymi graczami). Wszystkie ruchy gracza są publiczne, a więc widoczne dla przeciwnika - jedyną prywatną informacją są monety. Pod koniec gry ujawniane są wszystkie prywatne rzuty monetami, a sędzia wielozadaniowy używa tych żetonów monet i ruchów gracza, aby zdecydować, kto wygra.

  Według wyników gier, które są przedmiotem arbitrażu, przybliżenie prawdopodobieństwa wygranej pierwszego gracza jest w WYGODZIE, a także wyraźnie trudne dla PSPACE. Który (jeśli którykolwiek) to jest? Czy coś wiadomo na temat tego problemu?

Pamiętaj, że gracze mogą korzystać z mieszanych strategii, ponieważ w ten sposób możesz grać w gry o sumie zerowej (a la von Neumann).

DODANO MATERIAŁ:

Nazwijmy tę klasę złożoności RGUSP (wszystkie języki które można sprowadzić do gry referencyjnej z nieskorelowanymi półprywatnymi monetami, jak opisano powyżej, tak że jeśli , gracz 1 wygrywa z prawdopodobieństwem , a jeśli , gracz 1 wygrywa z prawdopodobieństwem ). Moje trzy powiązane pytania to:x ∈ L ≥ 2 / 3 x ∉ L ≤ 1 /$L$$x \in L$$\geq 2/3$$x \notin L$$\leq 1/3$

• Pytanie 2: RGUSP wydaje się dość solidny. Na przykład, jeśli zmienimy grę, aby sędzia nie wysyłał wiadomości, a jedynie obserwował wiadomości publiczne graczy 1 i 2 i odbierał od nich wiadomości prywatne, przybliżenie wartości tej gry jest nadal równoważne RGUSP. Chciałbym wykazać, że RGUSP jest solidny, dlatego chętnie dam nagrodę każdemu, kto znajdzie naturalną złożoność klasy C, tak aby PSPACE C RGUSP, gdzie żadna z obudów nie wydaje się być dokładna.$\subseteq$$\subseteq$

• Pytanie 3: Podejrzewam również, że klasa RGCSP (gry referencyjne ze skorelowanymi monetami półprywatnymi) jest WYŁĄCZNIE ukończona, a ja jestem również skłonny dać nagrodę komuś, kto udowodni ten fakt. W RGCSP, na pierwszym etapie, sędzia podaje dwóm graczom skorelowane losowe zmienne (na przykład może dać pierwszemu graczowi punkt w dużej płaszczyźnie rzutowej, a drugiemu linię zawierającą ten punkt). Następnie, dla wielomianowej liczby rund, dwaj gracze naprzemiennie wysyłają sobie nawzajem wiadomości publiczne o różnych rozmiarach. Po rozegraniu meczu sędzia wielozadaniowy decyduje, kto wygrał. Jaka jest złożoność przybliżenia prawdopodobieństwa wygranej dla gracza 1?

• Pytanie 4: Wreszcie mam pytanie, które może naprawdę dotyczyć kryptografii i rozkładów prawdopodobieństwa: Czy daje możliwość wykonania nieświadomego transferu do dwóch graczy w grze referencyjnej z nieskorelowanymi półprywatnymi monetami, pozwala im grać w dowolną grę referencyjną z powiązanymi monetami (lub alternatywnie, czy pozwala im zagrać w grę, w której zwycięzca jest ukończony EXPTIME)?

Nie mogę odpowiedzieć na moje pierwotne pytanie, ale mogę odpowiedzieć na pytanie 3 (i 4), które dodałem, gdy zaoferowałem nagrodę, ponieważ myślałem, że pierwotne pytanie było prawdopodobnie zbyt trudne. W rzeczywistości mam dwa dowody na pytanie 3.

Oto ustawienie pytania 3: Mamy sędziego wielomianowego, który na początku gry daje graczom 1 i 2 skorelowane zmienne losowe. Gracze 1 i 2 rozpoczynają grę bez ingerencji sędziego. Na koniec gry sędzia sprawdza zapis i decyduje, kto wygra. Mogę pokazać, że decyzja, kto wygra taką grę, jest WYŁĄCZENIEM, nawet jeśli otrzymujesz obietnicę, że zwycięzca wygra z prawdopodobieństwem co najmniej .$2/3$

======== Dowód 1 ============

Pierwszy dowód wykorzystuje fakt, że nieświadomy transfer jest uniwersalny dla bezpiecznego obliczeń dwóch stron. Tak więc, jeśli gracze 1 i 2 mogą wykonać nieświadome przeniesienie, mogą symulować arbitra w czasie wielomianowym, więc można zastosować poprzednie wyniki, o których mowa w zakończonych meczach.

Teraz, aby osiągnąć 1-2 nieświadome przeniesienie, na początku gry sędzia daje dwóm graczom dużą liczbę „nieświadomych przeniesień”. Opisujemy jedną z tych nieświadomych skrzynek transferowych. P1 otrzymuje dwie liczby losowe, i . P2 otrzymuje jedną z tych liczb losowych, i zmienną ( lub ), mówiącą, którą z liczb losowych P1 otrzymał. Aby wykonać nieświadomy transfer, P1 bierze dwa fragmenty danych, które chce przesłać, a XOR je za pomocą ir 2 r i i = 1 2 r 1 r $r_1$$r_2$$r_i$$i$$=1$$2$$r_1$$r_2$. P2 może następnie dekodować jeden z nich, ale P1 nie może powiedzieć, który P2 może dekodować. To 1-2 nieświadomy transfer. (Oczywiście, sędzia musi również dać graczom nieświadome pola przeniesienia skierowane w drugą stronę, od P2 do P1.)

Kiedy po raz pierwszy zadałem pytanie 4, martwiłem się, że bezpieczne wyniki obliczeń dwupartyjnych nie mają zastosowania do tego rodzaju interaktywnych obliczeń z sędzią, ale w rzeczywistości dość łatwo jest to wykazać.

=========== Dowód 2 ===========

Teraz drugi dowód na pytanie 3. Tutaj musimy wrócić i zmodyfikować dowód Feige-Kilian. W tym dowodzie rozważają maszynę Turinga, która wykonuje wykładnicze obliczanie czasu. Feige i Kilian kodują bitów na taśmie w czasie wielomianowym wielomianem x_1 x_n na dużym polu skończonym GF ( ). Teraz sędzia przyznaje punkt P1, a linia zawierająca ten punkt P2, a dwaj gracze przekazują ocenę punktu i linii . Sędzia używa wyszukiwania binarnego, aby znaleźć czas którym oceny P1 i P2 dla t Q t ( , … , ) p Q t t Q t Q t + $2^n$$t$$Q_t($$, \ldots,$$)$$p$$Q_t$$t$$Q_t$zgadzają się, ale ich oceny nie zgadzają się, po czym zadaje P1 sprytne pytanie, które ujawni, czy to ona kłamie.$Q_{t+1}$

Pierwszą rzeczą, której użyjemy, jest to, że nawet przy nieskorelowanych losowych monetach, sędzia może sprawić, że gracze 1 i 2 wykonają bit bitów, przekazując im dane XOR, które chcą zatwierdzić za pomocą losowych monet. Możemy więc mówić o tym, że P1 i P2 wkładają rzeczy do zapieczętowanych kopert.

Jedną rzeczą, którą możesz spróbować zasymulować dowód Feige-Kiliana jest: sędzia daje P1 wiele różnych punktów , a P2 dużo linii , tak że jest na . Teraz na każdym etapie wyszukiwania binarnego gracze umieszczają wartości i w zapieczętowanych kopertach, a następnie sędzia wybiera jedną losowo, aby gracze otworzyli. Dwaj gracze decydują, czy wartości są spójne, i odpowiednio kontynuują wyszukiwanie binarne. Teraz zrujnowaliśmy parę , ponieważ obaj gracze znają wartość punktu i linii, ale wciąż mamy wiele innych par (punkt, linia), których możemy użyć.ℓ i p i ℓ i Q t ( p i ) Q t ( ℓ i ) ( p i , ℓ i$p_i$$\ell_i$$p_i$$\ell_i$$Q_{t}(p_i)$$Q_t(\ell_i)$$(p_i, \ell_i)$

(W jaki sposób sędzia może losowo wybrać jedną jeśli daje graczom instrukcje tylko na początku gry? Może zakodować swoje instrukcje w XOR wartości, które przekazuje dwóm graczom na początku, oraz dwóch graczy nie może odczytać instrukcji, dopóki nie ujawnią wartości w odpowiednim czasie.)$(p_i, \ell_i)$

Ta strategia nie do końca działa, ponieważ P1 i P2 nie muszą być spójne co do czasu, w którym zaczynają leżeć z dwoma punktami (lub liniami) Oznacza to, że P1 może dać odpowiednią wartość dla i zła wartość dla . To całkowicie zepsułoby wyszukiwanie binarne i uczyniłoby protokół niejednoznacznym. Istnieje jednak fajna sztuczka, której możemy użyć, aby zmusić P1 do zachowania spójności. Dodaj kilka atrap punktów do zestawu punktów P1 i dodaj pozorne linieQ t ( p j ) p ′ k ℓ ′ $Q_t(p_i)$$Q_t(p_j)$${p}'_k$${\ell}'_k$do zestawu linii P2. Niech każda linia obojętna ma dwa punkty. Jeśli P1 zdarzy się, że poda prawidłową wartość dla jednego fikcyjnego punktu na linii i złą wartość dla drugiego fikcyjnego punktu, to ujawnił się jako kłamca, ponieważ P2 nie ma możliwości podania wartości dla linii, która jest popraw jeden z dwóch punktów P1 na nim, a nie drugi. Możemy zrobić podobną sztuczkę, aby konsekwentnie odpowiadać P2. Potem pozostaje tylko wykazanie, że ostatni krok dowodu Feige-Kiliana nadal działa. Okazuje się, że jest to proste, chociaż przejrzenie szczegółów znacznie wydłużyłoby tę odpowiedź.