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)
Dla wszystkich początkowych kombinacji w Kostce Rubika istnieje rozwiązanie, które wymaga <= 20 kroków, które go rozwiązuje.β
(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ł)β
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
- Czy jest na to sposób?
- Jakie są inne „praktyczne” zastosowania interaktywnych dowodów?
źródło
Odpowiedzi:
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).PH⊆P#P L∈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.
źródło
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=⟨U,U′,U2,D,D′,D2,⋯⟩ m ϵ π
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<m n≥m π A⊂G AM
Na przykład, zauważając, że i nazywając czas weryfikacji mieszania, myślę, że możemy obiecać:|s|=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 in≥m ϵ g∈G 18n|G| g s ≤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<m k=|A| g∈G g 18n2|G| ≤n
Tutaj myślę o jako, powiedzmy, , a jak, powiedzmy .ϵ 1109|G| k 110|G|
Standardowe uniwersalne sztuczki haszujące tworzą pojedynczy okrągły dowód Arthura-Merlina, że czas mieszania wynosi co najmniej .n
źródło