Jak nie rozwiązać P = NP?

Istnieje wiele prób udowodnienia albo albo P ≠ N P , i oczywiście wiele osób myśli o tym pytaniu, mając pomysły na udowodnienie obu kierunków.$\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Wiem, że istnieją metody, które okazały się nieskuteczne, i prawdopodobnie jest więcej takich, które miały historię niepowodzeń. Wydaje się również, że istnieją tak zwane bariery, których wielu prób dowodowych nie udało się pokonać.

Chcemy unikać dochodzenia w ślepych zaułkach, więc czym one są?

Powiedziałbym, że najbardziej znanymi barierami dla rozwiązania są$P=NP$

1. Relatywizacja (jak wspomniał Ran G.)
2. Naturalne dowody - przy pewnych założeniach kryptograficznych Rudich i Razborov udowodnili, że nie możemy udowodnić przy użyciu klasy dowodów zwanych dowodami naturalnymi.$P\neq NP$
3. Algebrization - autor: Scott Aaronson i Avi Wigderson. Dowodzą, że dowody, że algebrize nie mogą oddzielić i N $P$$NP$

Innym, który znam, jest wynik, że żadne sformułowanie LP nie może rozwiązać TSP (zostało to udowodnione przez Yannakakis dla symetrycznych LP i bardzo niedawno rozszerzone na ogólne LP). Oto post na blogu omawiający wynik.

Uwaga: Nie sprawdziłem jeszcze dokładnie odpowiedzi i brakuje części do napisania, rozważ ją jako pierwszą wersję roboczą.

Ta odpowiedź jest przeznaczona głównie dla osób, które nie są badaczami w teorii złożoności lub pokrewnych dziedzinach. Jeśli jesteś teoretykiem złożoności i przeczytałeś odpowiedź, daj mi znać, jeśli zauważysz jakiś problem lub masz pomysł, jak poprawić odpowiedź.

Gdzie można znaleźć zastrzeżone rozwiązania P vs. NP

• Istnieje strona P-versus-NP, która zawiera listę takich roszczeń.
• Artykuły podające się za rozstrzygające są regularnie publikowane na arXiv .

Inne listy, jak nie rozwiązywać P vs. NP

Lance Fortnow, So You Think You Settled P verus NP , 2009

Scott Aaronson, Eight Signs A Claimed P ≠ NP Proof Is Wrong , 2010

Strona Polymath dla artykułu Deolalikar , na której sekcja z dalszymi czytaniami zawiera ładną listę referencji na temat problemu.

Jak nie podchodzić do P vs. NP

Pozwól mi omówić „jak nie podchodzić do P vs. NP” nie w sensie pomysłów, które nie będą działać, ale w bardziej ogólnym sensie. P vs. NP to łatwy do stwierdzenia problem (patrz także moja odpowiedź tutaj ):

NP = P: Dla każdego problemu decyzyjnego z algorytmem wielomianowego weryfikatora czasu istnieje algorytm wielomianowy.

lub równoważnie

Istnieje algorytm wielomianowy dla SAT.
SAT można zastąpić dowolnym innym problemem NP-zupełnym .

.

Często ludzie nadmiernie upraszczają i nadmiernie filofilizują problem i wyolbrzymiają jego praktyczne znaczenie (jak wspomniano powyżej). Takie stwierdzenia często mają na celu dać intuicję, ale w żaden sposób nie zastępują matematycznego stwierdzenia problemu.

Wydajność teoretyczna to nie to samo co wykonalność w praktyce.

Pozwól mi najpierw przesadzić z praktycznymi konsekwencjami.

I. Możliwe, że P = NP, ale w praktyce nie pomaga to w żadnym problemie!

Powiedz na przykład, że SAT jest w P, ale najszybszym algorytmem dla jego czasu działania jest . Ten algorytm nie ma praktycznego zastosowania.$2^{2^{64}} n^{65536} + 2^{2^{128}}$

II. Możliwe, że P NP i my możemy skutecznie rozwiązać problemy z kompletnością NP .$\neq$

Powiedz na przykład, że SAT nie jest w P, ale ma algorytm z czasem działania .$n^{\lg^*\lg^* n}$

Aby uzyskać dane wejściowe, które sprawiłyby, że , musisz użyć więcej elektronów, niż sądzi się we wszechświecie. Zatem wykładnik wynosi zasadniczo 2 .$\lg^* n > 6$$2$

Chodzi tutaj przede wszystkim o to, że P jest abstrakcyjnym prostym modelem wydajnego obliczenia, a najgorszym przypadkiem złożoność jest abstrakcyjnym prostym modelem szacowania kosztów obliczeń itp. Wszystkie te są abstrakcjami, ale w praktyce nikt nie rozważałby algorytmu tak jak ten w (I) powyżej jako naprawdę wydajny algorytm. P jest ładnym modelem abstrakcyjnym, ma ładne właściwości, sprawia, że ​​problemy techniczne są łatwe i jest przydatny. Jednak jak każda abstrakcja matematyczna kryje w sobie szczegóły, o które w praktyce możemy się troszczyć. Istnieje wiele bardziej wyrafinowanych modeli, ale im bardziej skomplikowany model, tym mniej przyjemnie byłoby się kłócić.

Co ludzie dbają o to, aby w praktyce obliczyć to odpowiedź na problem dla instancji, że dbają oni o użyciu wystarczającą ilość zasobów. Są zależne od zadania i należy je wziąć pod uwagę.

Próba znalezienia lepszych algorytmów dla praktycznych przypadków problemów trudnych dla NP jest interesującym i godnym wysiłkiem. Istnieją algorytmy heurystyczne SOL-SOLVER, które są stosowane w branży i mogą rozwiązać praktyczne przypadki SAT za pomocą milionów zmiennych. Istnieje nawet Międzynarodowy Konkurs SAT .

(Ale są też małe konkretne przypadki, w których wszystkie te algorytmy zawodzą i bardzo zawodzą, możemy faktycznie udowodnić, że wszystkie najnowocześniejsze rozwiązania SAT zajmują wykładniczy czas, aby rozwiązać proste przypadki, takie jak propozycyjna zasada Pigeonhole .)

Należy pamiętać, że poprawności i czasu działania programów nie można uzyskać po prostu uruchamiając program w instancjach . Nie ma znaczenia, ile wystąpień próbujesz, żadna kwota nie jest wystarczająca. Istnieje nieskończenie wiele możliwych danych wejściowych i musisz wykazać poprawność i wydajność (tj. Czas działania jest wielomianowy) programu dla wszystkich z nich. Krótko mówiąc, potrzebujesz matematycznego dowodu poprawności i wydajności. Jeśli nie wiesz, co to jest dowód matematyczny, powinieneś najpierw nauczyć się podstawowej matematyki (przeczytaj podręcznik dyskretna matematyka / kombinatoryka / teoria grafów, to dobry temat, aby dowiedzieć się, co jest uważane za dowód matematyczny).

Uważaj także na inne twierdzenia dotyczące P vs. NP i konsekwencje ich odpowiedzi. Takie twierdzenia często opierają się na podobnych uproszczeniach.

Teoretycy złożoności tak naprawdę nie dbają o odpowiedź na P vs. NP!

Trochę przesadziłem. Oczywiście zależy nam na odpowiedzi na P vs. NP. Ale zależy nam na tym w kontekście. P vs. NP jest naszym sztandarowym problemem, ale nie jest ostatecznym celem. Jest to problem łatwy do stwierdzenia, zawiera wiele podstawowych pomysłów, jest przydatny do wyjaśnienia interesujących nas pytań osobom, które nie znają tematu. Ale nie szukamy ani odrobiny odpowiedzi Tak / Nie na pytanie.

Poszukujemy lepszego zrozumienia natury wydajnych obliczeń . Wierzymy, że rozwiązanie tego problemu przyniesie takie zrozumienie i to jest prawdziwy powód, dla którego się tym zajmujemy. Jest to część ogromnego zbioru badań. Jeśli chcesz posmakować tego, co robimy, zajrzyj do dobrego podręcznika teorii złożoności, np. Arory i Baraka „ Teoria złożoności: nowoczesne podejście ” ( wersja robocza ).

$\neq$

Krótko mówiąc, z perspektywy teoretyka złożoności

P vs. NP nie jest łamigłówką z odpowiedzią Tak / Nie. Szukamy odpowiedzi na P vs. NP, ponieważ uważamy, że pozwoli to lepiej zrozumieć naturę wydajnych obliczeń. Odpowiedź bez większego postępu w naszym rozumieniu nie jest bardzo interesująca.

Było zbyt wiele razy, gdy nie-eksperci domagali się rozwiązań dla P vs. NP, a te twierdzenia zwykle cierpią z powodu problemów, których nie zrobiliby, gdyby tylko przeczytali standardowy podręcznik na temat teorii złożoności.

Typowe problemy P = NP

Stwierdzenia P = NP wydają się być bardziej powszechne. Myślę, że następujące jest najczęstszym typem. Ktoś ma pomysł, pisze program i testuje go w kilku przypadkach i uważa, że ​​jest to czas wielomianowy i poprawnie rozwiązuje problem NP-zupełny. Jak wyjaśniłem powyżej, żadna ilość testów nie pokaże P = NP. P = NP potrzebuje matematycznego dowodu , a nie tylko programu, który wydaje się rozwiązać problem NP-zupełny w czasie wielomianowym.

Te próby zwykle wiążą się z jednym z dwóch problemów:

I. algorytm nie jest tak naprawdę czasem wielomianowym.

II. algorytm nie rozwiązuje poprawnie wszystkich instancji.

$\neq$

[do napisania]

Jak sprawdzić, czy algorytm tak naprawdę nie działa

Nie można pokazać, że algorytm działa poprawnie, testując. Ale możesz pokazać, że nie działa poprawnie, testując! Oto, w jaki sposób możesz upewnić się, że algorytm nie jest poprawny, jeśli chcesz wykonać jakąś pracę.

Najpierw napisz program, który konwertuje instancje SAT (w standardowym formacie CNF) na rozwiązywany przez Ciebie problem NP-trudny. SAT jest jednym z najlepiej zbadanych problemów trudnych dla NP, a redukcja z innych problemów do SAT jest zazwyczaj łatwa. Po drugie, weź przykłady, z którymi zmagają się najnowocześniejsze solwery SAT (np. Weź przykłady z konkurencji SAT) i podaj je do swojego algorytmu i zobacz, jak działa Twój algorytm. Wypróbuj znane trudne instancje, takie jak propozycyjna Zasada Pigeonhole (i nie oszukuj, kodując je jako specjalne przypadki), instancje kryptograficzne (takie jak Wyzwania Faktorowania RSA ), losowe instancje k-SAT w pobliżu progu itp.

$10 n^2$

Jak sprawdzić algorytm P = NP idea nie może działać

Jeśli to zrobisz, będziesz całkiem pewien, że twój algorytm nie działa (jeśli działa lepiej niż najnowocześniejsze solwery SAT, konkuruj w następnym konkursie i wiele osób byłoby zainteresowanych studiowaniem twojego algorytmu i pomysłów).

Teraz wiesz, że to naprawdę nie działa, ale to nie wystarczy. Chcesz wiedzieć dlaczego

czy powodem, dla którego mój algorytm nie działa, jest mały problem, który można naprawić, czy też istnieje podstawowy powód, dla którego nie może on działać?

Czasami problem z algorytmem jest prosty i można zidentyfikować, co było nie tak koncepcyjnie. Najlepszy wynik to to, że rozumiesz powód, dla którego twój pomysł nie działa. Często tak nie jest, twój pomysł nie działa, ale nie możesz zrozumieć, dlaczego. W takim przypadku należy pamiętać:

zrozumienie, dlaczego jakiś pomysł nie może działać, może być trudniejsze niż rozwiązanie P vs. NP!

Jeśli potrafisz wystarczająco sformalizować swój pomysł, możesz być w stanie udowodnić ograniczenia określonych pomysłów (np. Istnieją wyniki, które mówią, że określone formalizacje zachłannego algorytmu nie są w stanie rozwiązać problemów z NP-zupełnością). Jest to jednak jeszcze trudniejsze i nie masz dużej szansy, jeśli nie przeczytałeś standardowego podręcznika teorii złożoności.

Czasami nie ma nawet jasnego koncepcyjnego pojęcia, dlaczego algorytm powinien działać, tj. Jest oparty na niektórych niezbyt dobrze poznanej heurystyce . Jeśli nie masz jasnego koncepcyjnego pojęcia, dlaczego twój algorytm powinien działać, możesz nie mieć dużej szansy na zrozumienie, dlaczego on nie działa!

$\neq$

$\neq$

Problem 1: autor nie zna definicji P i NP, a nawet gorzej nie rozumie, co jest dowodem matematycznym. Ponieważ autorowi brakuje podstawowego szkolenia matematycznego, nie rozumie, kiedy mówi mu się, co przedstawia, co nie jest dowodem (np. Kroki nie wynikają z poprzednich).

Problem 2: autor myli „nie wiemy jak” z „matematyczną niemożliwością”. Na przykład przyjmują różne nieuzasadnione założenia, a na pytanie „dlaczego to stwierdzenie jest prawdziwe?” odpowiadają „jak to może być fałsz?”. Jednym z powszechnych jest założenie, że każdy program rozwiązujący problem musi przejść określone kroki, np. Musi obliczyć określone wartości pośrednie, ponieważ nie może wymyślić alternatywnego sposobu rozwiązania problemu.

[do uzupełnienia]

$\neq$

[do napisania]

$\neq$

Jeśli roszczenie nie cierpi z powodu tych podstawowych problemów, odrzucenie go staje się trudniejsze. Na pierwszym poziomie można znaleźć niepoprawny krok w argumencie. Typowa odpowiedź autora jest taka, że ​​mogę to naprawić, a to tam iz powrotem może trwać. Podobnie jak w przypadku rozwiązań P = NP, często bardzo trudno jest znaleźć podstawowy problem z pomysłem, który może pokazać, że nie może on działać, szczególnie gdy sam pomysł jest nieformalny.

$\neq$

Być może najczęstszą techniką, której nie można zastosować, jest relatywizacja , czyli posiadanie bazy TM z dostępem do Oracle.

$A$$B$$\text{P}^A = \text{NP}^A$$\text{P}^B \ne \text{NP}^B$

$\text{P}\ne \text{NP}$$O$$\text{P}^O \ne \text{NP}^O$$A$

$\text{P} \stackrel{?}{=} \text{NP}$

Sugeruję przeczytanie tego posta na blogu autorstwa Lance'a Fortnowa :

1. Więc myślisz, że osiedliłeś P verus NP Mylisz się. Rozwiązać. Czasami nadal możesz uratować coś interesującego ze swojego wadliwego dowodu.
2. Uważasz, że dowód jest poprawny. Twoje przekonanie jest nieprawidłowe. Wróć do kroku 1.
3. Czy robisz jakieś założenia lub skróty, nawet pozornie małe i oczywiste? Czy używasz słów takich jak „wyraźnie”, „oczywiście”, „dobrze widać”, „należy”, „trzeba” lub „prawdopodobnie”? Twierdzisz, że rozstrzygnąłeś chyba najważniejsze pytanie w całej matematyce. Nie możesz zakładać. Wróć do kroku 1.
4. $n^k$
5. Prześlij swój artykuł do archiwum on-line. Być może niektórzy mówią ci, czego brakuje lub co jest nie tak w twoim dokumencie. Powinno to sprawić, że przejdziesz do kroku 1. Zamiast tego wprowadzasz kilka bezsensownych zmian w swoim artykule i repost.
6. W końcu ludzie ignorują twój papier. Zastanawiasz się, dlaczego nie zdobywasz sławy i fortuny.
7. Prześlij swój artykuł do dziennika.
8. Artykuł został odrzucony. Jeśli jesteś mądry, wrócisz do kroku 1. Ale jeśli będziesz mądry, nigdy nie przejdziesz do kroku 7.
9. Skarżysz się redaktorowi, że albo redaktor nie rozumie dowodu lub że można go łatwo naprawić. Jesteś zszokowany, że szanowany redaktor lub czasopismo tak potraktują twój artykuł.
10. Ponownie prześlij gazetę, odwołaj się, wypróbuj inne czasopisma - wszystko bezskutecznie.
11. Jesteś przekonany, że „zakład” celowo tłumi twój papier, ponieważ nasza dziedzina stałaby się znacznie mniej interesująca, gdybyśmy rozwiązali problem P w porównaniu z NP, więc musimy zachować go za wszelką cenę.
12. Jeśli powiem ci inaczej, uwierzyłbyś mi?

tutaj jest nieco niejasny / głęboki / trudny / kąt wewnętrzny / odniesienie / zwrot związany z podejściami przez obwody z lat 80. XX wieku, które pierwotnie wskazał mi przed laty Luca Trevisan w innym miejscu w cyberprzestrzeni, a także powtórzył Stasys Jukna, autor znakomitego odniesienie do tematu, Boolean Function Complexity: Advances and Frontiers (Algorytmy i kombinatoryki, t. 27 ).

można zauważyć wcześniejszy trend w niektórych myślach Razborowa, który ostatecznie doprowadził do opracowania Natural Proofs (tzw. „naturalizacja”). ref [273] jest bardzo techniczny i trudny i nie wydaje się, aby był cytowany, budowany / rozszerzany lub powtarzany w późniejszych artykułach / książkach, chociaż Naturalne Dowody mogą być postrzegane jako późniejsze duże uogólnienie. fragment pochodzi z doskonałej referencji John E Savages Models of Computation p457

$\Omega(n^2)$$n$

[270] AA Razborov, „Dolne granice monotonicznej złożoności niektórych funkcji logicznych”, Dokl. Akad Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801, (po rosyjsku); Tłumaczenie na język angielski w radzieckiej matematyce. Dokl. 31 (1985), 354–357

[271] AA Razborov, „Dolna granica złożoności sieci monotonicznej logicznego stałego”, Mat. Zametki 37 (1985), 887–900, (po rosyjsku); Tłumaczenie na język angielski w matematyce. Uwagi 37 (6) (1985), 485–493.

[273] AA Razborov, „O metodzie aproksymacji”, Proc. 21 Ann. ACM Symp. Teoria obliczeń (1989), 167–176.