Interaktywny dowód liczby Boga?

Ostatnio uczyłem się o interaktywnych dowodach i zastanawiałem się, czy cała ta sprawa była jedynie ciekawostką teoretyczną, czy też miała jakieś praktyczne zastosowania. Myślałem, że zacznę od przykładu, który przyszedł mi do głowy pod prysznicem:

Ostatnio ogłaszano, że „liczba Boga” = 20. (Liczba Boga to minimalna liczba kroków potrzebnych do rozwiązania Kostki Rubika). Chociaż jest to dość interesujące, wydaje się, że jest trochę zwrotów ... To nie jest „normalny” dowód w podręczniku, sens wielomianowy możliwy do zweryfikowania w czasie. Ten dowód ma wyraźnie „brutalną siłę” - mam na myśli, że kolesie w laboratorium Dr Morleya próbowali z miliardami i miliardami kombinacji kostek w ogromnych superkomputerach Google, aby znaleźć tę schludną, ciasną dolną granicę.

W każdym razie pytanie brzmi: skąd możemy mieć pewność, że dr Morley Davidson i jego zespół są uczciwi? Cóż, od razu może wyrzucić argument z autorytetu przez okno, ponieważ nie jest to matematycznie rygorystyczne. Oczywistą alternatywą jest ponowna weryfikacja dowodu przez sprawdzenie kodu źródłowego i ponowne uruchomienie całej sprawy, co wydaje się strasznym marnotrawstwem zasobów obliczeniowych, nie wspominając o tym, że każdy, kto chciałby być przekonany o tym, trzeba to zrobić na własnym stanowisku roboczym - bardzo żmudna i nieprzyjemna propozycja dla prawdziwego sceptyka. Wydaje się więc, że jest to swoista deilema ontologiczna.

Uważam więc, że jest to dokładnie taka sytuacja, w której potrzebujemy interaktywnego dowodu . Superkomputer Google może być wszechpotężnym, ale zwodniczym Prover, a my sceptyczni, jeśli nie analni członkowie społeczeństwa, to Wielomianowo ograniczeni Weryfikatorzy. Gdybyśmy mogli jakoś zapytać naszą „Wyrocznię” wielomianowo wiele razy i byliby przekonani o tej dolnej granicy, moglibyśmy być przekonani o tym, że ma rację, ponad wszelką uzasadnioną wątpliwość.

Wygląda więc na to, że problem decyzyjny „Liczba Boga wynosi <20” leży w lub może zostać przekształcony w następujący sposób (nieformalnie)$\Pi_2^p$

Dla wszystkich początkowych kombinacji w Kostce Rubika istnieje rozwiązanie, które wymaga <= 20 kroków, które go rozwiązuje.$\alpha$$\beta$

(nie jestem pewien, czy to prawda, ale zarówno i mają małe rozmiary, biorąc pod uwagę konfigurację początkową i rozwiązanie, łatwo jest sprawdzić, czy rzeczywiście rozwiązuje moduł)$\alpha$$\beta$

a problem decyzyjny „Boska liczba to 20” można przekształcić jako

Liczba Boga wynosi <20 i istnieje rozwiązanie dla początkowej kombinacji kostki Rubika, która wymaga 20 kroków.

Prawdopodobnie jest na to dowód IP [n]. (jeszcze raz sprawdź moje działania)

Moje pytanie jest dwojakie

1. Czy jest na to sposób?
2. Jakie są inne „praktyczne” zastosowania interaktywnych dowodów?

... wydaje się, że problem decyzyjny „Liczba Boga wynosi <20” leży w .$\Pi_2^p$

To wystarczy, aby mieć interaktywny dowód. W rzeczywistości Lund i in. udowodnił, że każdy język w hierarchii wielomianowej (PH) ma interaktywny dowód, używając twierdzenia Tody ( ). Zmniejszyli do # P-zupełnego języka PERMANENT i udostępnili metodę algebraiczną, której można użyć do interaktywnego udowodnienia PERMANENTU. (Jest to bardzo niedokładne; więcej informacji można znaleźć w artykule).$\rm{PH} \subseteq P^{\#P}$$L\in \rm{PH}$

Używając swoich technik, Shamir udowodnił, że IP = PSPACE .

Wcześniej udowodniono, że wszystkie IP mają dowody zerowej wiedzy , więc:

Wszystkie języki w PSPACE mają interaktywne dowody zerowej wiedzy.

Ustalenie, że jest średnicą (liczbą Boga) grupy Kostki Rubika w metrze półobrotu z zestawem generującym Singmaster był cudownym rezultatem. Jestem ciekaw dalszych pytań, takich jak określanie ile półobrót skręca zajęłoby dostać kostkę pełni „mieszane” do -Zamknij się do równomiernego rozprowadzania stacjonarny . $20$$G$$s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$$m$$\epsilon$$\pi$

Uważam, że takie mieszanie wykazuje punkt odcięcia, w którym dla niektóre konfiguracje są znacznie bardziej prawdopodobne niż inne, podczas gdy dla sześcian jest prawie całkowicie zakodowany do jednolitego rozkładu i nie ma dużego podzbioru konfiguracji jest niekorzystny. W sercu każdego miksowania, które wykazuje takie odcięcie, może być obietnica. Obietnicę tę można wykorzystać do stworzenia protokołu Arthur-Merlin .$n\lt m$$n\ge m$$\pi$$A\subset G$ $\mathsf{AM}$

Na przykład, zauważając, że i nazywając czas weryfikacji mieszania, myślę, że możemy obiecać:$\vert s \vert=18$$m$

• Jeśli to dla wszystkich, z wyjątkiem bardzo małej liczby , elementów istnieją bardzo bliskie sposobom pisania jako słów o długości i$n\ge m$$\epsilon$$g\in G$$\frac{18^n}{\vert G \vert}$$g$$s$$\le n$

• Jeśli , to jest znacznie większa liczba, , elementów gdzie można zapisać tylko co najwyżej sposoby jako słowa długości .$n \lt m$$k=\vert A\vert$$g\in G$$g$$\frac{18^n}{2 \vert G \vert}$$\le n$

Tutaj myślę o jako, powiedzmy, , a jak, powiedzmy .$\epsilon$$\frac{1}{10^9}\vert G\vert$$k$$\frac{1}{10}\vert G\vert$

Standardowe uniwersalne sztuczki haszujące tworzą pojedynczy okrągły dowód Arthura-Merlina, że ​​czas mieszania wynosi co najmniej .$n$

1. Arthur wybiera losowy element , bezładny mieszania odwzorowywania słów z na zestaw rozmiarów i losowy obraz o$g\in G$$h$$G$$\frac{18^n}{\vert G \vert}$$y$$h$
2. Merlin mówi Arthurowi słowo o długości do które przy zastosowaniu do początkowej pozycji sześcianu równa się$W$$n$$g$
3. Słowo musi również spełniać - wskazując, że prawdopodobnie istnieje wiele słów o długości które są równe$W$$h(W)=y$≤ n g$\le n$$g$
4. Arthur i Merlin powtarzają, aby wzmocnić w razie potrzeby

Ponieważ, jak sądzę, w przypadku grup czas mieszania jest co najmniej średnicą (liczbą Boga), stanowi to również dowód Arthura-Merlina na ograniczenie liczby Bożej dużej grupy.