Interaktywny dowód liczby Boga?

12

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)Π2p

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

  1. Czy jest na to sposób?
  2. Jakie są inne „praktyczne” zastosowania interaktywnych dowodów?
Gabgoh
źródło
Myślę, że masz na myśli, że „liczba Boga” to maksymalna liczba ruchów potrzebnych do rozwiązania Kostki Rubiksa. Podobnie wspominasz kilka razy „tę schludną, ciasną dolną granicę”, a masz na myśli „górną granicę”.
Ross Snider
1
W każdym razie częściowa odpowiedź na twoje pytanie. Istnieje prawdopodobnie powiązane pytanie cstheory.stackexchange.com/questions/2461/… . Według mnie odpowiedź na twoje pierwsze pytanie brzmi „tak” - wystarczy postępować zgodnie z protokołem. Rozumiem jednak również, że faktyczne zaangażowanie w interaktywne ustawienia próbne nie „przyłapało”. Czy ktoś wie, czy zaangażowane stałe są bardzo wysokie?
Ross Snider
@Ross Snider: przepraszam, mój błąd :( Poprawiony. Co do twojego drugiego punktu, tak. Jednak nie sądzę, że problem dotyczy dużych stałych w Weryfikatorze, ale zbyt dużego obciążenia „Provera”. IP [n] wymagałoby, aby Weryfikator był znacznie potężniejszy niż (gdzie jest Google), ale w rzeczywistości procedura wymagałaby większej mocy niż , co czyni go „niepraktycznym”, przypuszczam, że opublikowany link był bardzo pomocny, dziękujęΠ2PSPACE
gabgoh

Odpowiedzi:

10

... wydaje się, że problem decyzyjny „Liczba Boga wynosi <20” leży w .Π2p

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).PHP#PLPH

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.

MS Dousti
źródło
Ale udowodnienie czegoś w za pomocą interaktywnego dowodu ogólnie oznacza rozwiązanie problemu P ( cstheory.stackexchange.com/questions/2461/... ), więc jeśli szukasz praktycznych interaktywnych dowodów , to nie zrobi tego. Π2#P
Peter Shor
@Peter: Jeśli przez „praktyczny” rozumiesz, że prover to BPP, masz rację. W rzeczywistości tylko języki NP mają takie dowody.
MS Dousti
Miałem na myśli „praktyczne” coś, w przypadku czego przysłowie ma mniej więcej taką samą moc obliczeniową, jak dowód, że liczba Boga = 20
Peter Shor
1
Dziękuję za odpowiedź, ale jak komentuje Shor, przez „praktyczne” mam na myśli coś, co może faktycznie być możliwe do wdrożenia, co do zasady niemożliwe. Oto sedno tego, oto przykład „praktycznego” systemu dowodowego, który niczego nie dowodzi. [Daję proverowi losową konfigurację początkową , a prover zwraca sekwencję ruchów w mniej niż 20 krokach, co rozwiązuje ten problem. Próbuję tego kilka razy.] Oczywiście to nie zadziała, ale tego właśnie szukam. α
gabgoh
2
@sadeq: Być może niektóre problemy na MA i AM mogą, ale nie jestem świadomy niczego poza tymi klasami, które mają „praktyczne” interaktywne dowody.
Peter Shor
1

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 . 20Gs=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<mnmπAG AM

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

  • 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 inmϵgG18n|G|gsn

  • 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<mk=|A|gGg18n2|G|n

Tutaj myślę o jako, powiedzmy, , a jak, powiedzmy .ϵ1109|G|k110|G|

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 ogGhG18n|G|yh
  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ęWng
  3. Słowo musi również spełniać - wskazując, że prawdopodobnie istnieje wiele słów o długości które są równeWh(W)=yn gng
  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.

Znaki
źródło