Poszukuję źródła literatury do naśladowania

Jestem pewien, że nie jako pierwszy rozważyłem pomysł, który zamierzam przedstawić. Przydałoby się jednak znalezienie literatury związanej z tym pomysłem.

Chodzi o to, aby zbudować Maszynę Turinga M z właściwością, że jeśli P = NP, wówczas M rozwiąże 3-SAT w czasie wielomianowym. (Wybór 3-SAT jest arbitralny. To może być naprawdę dowolny problem w NP).

Dla jasności nie jest to twierdzenie, że P = NP. W rzeczywistości uważam, że jest odwrotnie. Po prostu stwierdzam, że jeśli P = NP, to M dostarczy rozwiązanie wielomianowe. Jeśli szukasz skutecznego rozwiązania, powinienem ostrzec, że jest to dalekie od skutecznego.

M jest skonstruowany w następujący sposób: po pierwsze, załóż kodowanie kanoniczne dla wszystkich maszyn Turinga i zastosuj numerację na tych maszynach. Istnieje więc maszyna Turinga nr 1, liczba 2 itd. Idea uniwersalnej maszyny Turinga, która potrafi odczytać format dostarczonej maszyny, a następnie symulować działanie tej maszyny na osobnym wejściu, jest dość dobrze znana. M zastosuje uniwersalną maszynę Turinga do budowy i symulacji kolejno każdej maszyny Turinga.

Najpierw symuluje działanie maszyny Turinga 1 dla jednego kroku.
Następnie analizuje wydajność maszyny Turinga 1.
Symuluje działanie maszyny Turinga 1 dla dwóch etapów i analizuje wyniki, a następnie przechodzi do symulacji maszyny Turinga 2 dla dwóch kroków. Kontynuuje i zapętla w ten sposób, z kolei uruchamiając maszynę Turinga 1 dla k kroków, a następnie 2 dla k kroków ... a następnie ostatecznie k dla maszyny k dla kroków.

Po każdym uruchomieniu symulacji bada jego wynik. Jeśli wyjście jest przypisaniem zmiennych spełniających problem 3-SAT, M zatrzymuje się w stanie akceptacji. Z drugiej strony, jeśli dane wyjściowe są ciągiem sprawdzającym w jakimś weryfikowalnym języku sprawdzającym, z udowodnionym wynikiem, że wystąpienie problemu nie jest zadowalające, M zatrzymuje się w stanie odrzucenia. (W przypadku języka próbnego moglibyśmy na przykład użyć aksjomatów Peano z logiką drugiego rzędu i podstawowych aksjomatów logicznych w stylu Hilberta. Pozostawiam to dla czytelnika ćwiczenie, aby dowiedzieć się, że jeśli P = NP, poprawne język sprawdzający istnieje i jest weryfikowalny w czasie wielomianowym).

Twierdzę tutaj, że M rozwiąże 3-SAT w czasie wielomianowym wtedy i tylko wtedy, gdy P = NP. W końcu algorytm znajdzie magiczną maszynę Turinga o numerze K, która okazuje się być skutecznym rozwiązaniem dla problemu 3-SAT, i jest w stanie udowodnić swoje wyniki dla powodzenia lub niepowodzenia. K będzie w końcu symulowany podczas wykonywania kroków poli (strlen (wejściowych)) dla niektórych wielomianów. Wielomian dla M jest w przybliżeniu kwadratem wielomianu dla k w największym współczynniku, ale z pewnymi straszliwymi stałymi w wielomianu.

Powtórzę tutaj moje pytanie: chcę wiedzieć, czy istnieje źródło literatury, które wykorzystuje ten pomysł. Nieco mniej interesuje mnie omawianie samego pomysłu.

Wygląda na to, że pomysł ten przypisuje się Levinowi (nazywa się to optymalnym wyszukiwaniem). Wierzę, że ten fakt jest dobrze znany. Podobny algorytm jest opisany na przykład w Wikipedii , chociaż wykorzystuje problem sumy podzbiorów. W tym artykule ze scholarpedii można znaleźć kilka odniesień na ten temat, w tym wskaźnik do oryginalnego algorytmu i niektórych innych optymalnych algorytmów wyszukiwania.

$\varphi$$P=NP$$\varphi$

Komentarz 2: Jak zauważył Jarosław Blasiok w innej odpowiedzi, algorytm ten nie decyduje o Sat tylko zakładając, że P = NP.

Pomysł uruchomienia po przekątnej wszystkich możliwych maszyn Turinga był wcześniej używany przez Leonida Levina w tak zwanej obecnie Uniwersalnej wyszukiwarce Levins. Niestety, w przeciwieństwie do niezwykle powszechnego nieporozumienia, dla tego, co wiem, odmiany uniwersalnego wyszukiwania Levinsa NIE są w stanie zapewnić jawnego algorytmu rozwiązywania SAT (problemu decyzyjnego) w czasie wielomianowym, biorąc pod uwagę jedynie założenie, że P = NP - i żaden twój algorytm nie robi .

Zastrzeżenie proponowanego rozumowania leży (jak często) w „łatwym ćwiczeniu pozostawionym czytelnikowi” - sam nie byłem w stanie udowodnić tego ćwiczenia i nie wierzę, że jego stwierdzenie jest prawdziwe, a mianowicie:

Zakładając, że P = NP, istnieje wielomianowy rozmiar ZFC świadczy o niezadowalaniu danej formuły boolowskiej.

Co więcej: Nie widzę, jak udowodnić istnienie wielomianowo krótkiego ZFC dowodzi niezadowolenia przy (silniejszym) założeniu, że „P = NP jest możliwe do udowodnienia w ZFC”. Staje się to jednak łatwe przy jeszcze silniejszych założeniach, a mianowicie:

(*) Istnieje maszyna M działająca w czasie wielomianowym, która w sposób pewny rozwiązuje SAT.

I to jest, moim zdaniem, prawidłowe założenie, zgodnie z którym twój algorytm rozwiązuje SAT w czasie wielomianowym. Powyżej słowa „możliwe do rozwiązania SAT” mam na myśli: istnieje maszyna M i dowód ZFC, że M rozwiązuje SAT.

Zauważ, że to założenie jest wciąż nieco słabsze niż następujące: (**) Istnieje maszyna M, która prawdopodobnie działa w czasie wielomianowym i prawdopodobnie rozwiązuje SAT.

W (**) można mieć wyraźną konstrukcję, która osiąga ten sam cel, który jest jeszcze prostszy: wylicz wszystkie dowody ZFC, aż znajdziesz właściwą maszynę M (spędzanie stałego czasu), a następnie uruchom M w danej instancji.

Prawdą jest jednak, że przy założeniu P = NP istnieje pewien system sprawdzania wielomianowo weryfikowalnego z krótkimi dowodami na niespełnienie danej formuły. Niestety nie znamy ani systemu dowodowego, ani weryfikatora pod ręką i nie jest to pomocne w tym ustawieniu.

$f^{-1}(x)$

Pamiętaj, że ten schemat dotyczy na przykład problemu FAKTORING; tutaj f to tylko mnożenie (zdefiniowane tylko dla czynników innych niż \ pm 1), a B to sprawdzanie pierwotności. Stąd uniwersalne wyszukiwanie Levinsa byłoby (do stałego współczynnika) optymalnym algorytmem dla FACTORING. Biorąc pod uwagę, że optymalny algorytm jest wolniejszy niż znany algorytm sprawdzania pierwotności - w innym przypadku sprawdzanie pierwotności staje się dominujące.

$NP\cap co-NP$