Jak nie rozwiązać P = NP?

96

Istnieje wiele prób udowodnienia albo albo PN P , i oczywiście wiele osób myśli o tym pytaniu, mając pomysły na udowodnienie obu kierunków.P=NPPNP

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ą?

Raphael
źródło
16
Myślę, że lepiej jest być wiki społeczności (ponieważ nie ma jednoznacznej odpowiedzi na to pytanie, jest ono zbyt szerokie).
6
@SaeedAmiri Nie. Społeczność Wiki była alibi, pozwalając na pytania, które nie były odpowiednie dla platformy Stack Exchange, ale nie jest to już zrobione .
Gilles
4
Uwaga moderatora: to pytanie jest szersze niż normalne pytanie wymiany stosu, ale staramy się zbudować kanoniczną parę pytań i odpowiedzi. Jeśli uważasz, że to pytanie nie powinno istnieć w obecnej formie, omów je na naszej stronie meta .
Gilles
w przypadku podobnego pytania ze strony przeciwnej / konstruktywnej zobacz, jak można rozwiązać teorie i zapytania w dziedzinie informatyki?
vzn
4
Odpowiedź wag: arXiv jest skarbnicą sposobów, aby tego nie robić.
pseudonim

Odpowiedzi:

76

Powiedziałbym, że najbardziej znanymi barierami dla rozwiązania 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.PNP
  3. Algebrization - autor: Scott Aaronson i Avi Wigderson. Dowodzą, że dowody, że algebrize nie mogą oddzielić i N PPNP

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.

Optować
źródło
4
Ważne linki: o barierach ogólnie i przykładach zabawek . Ponadto powinieneś uważać na ostatnie zdanie, myślę, że rozsądnie byłoby zamieścić link do postu na blogu, który wyjaśnia, dlaczego TSP nie do wykonania przez ogólny wynik LP nie dowodzi , ponieważ ludzie mogą być zdezorientowani fakt, że PR jest P -Complete. PNPP
Artem Kaznatcheev
1
Jeśli chcesz poprawić odpowiedź (nie jest jeszcze w pełni gotowa do przyjęcia), dodaj krótkie wyjaśnienia i linki do szczegółów, aby ciekawy czytelnik wiedział, o czym mówisz.
Raphael
57

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.2264n65536+22128

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

Powiedz na przykład, że SAT nie jest w P, ale ma algorytm z czasem działania .nlglgn

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 .lgn>62

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 ).

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.

[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.

10n2

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!

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]

[do napisania]

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.

Kaveh
źródło
Mimo że podoba mi się strona P-kontra-NP, denerwuje mnie to, że nie śledzi, które dowody zostały wycofane przez ich autorów. W przypadku niektórych linków arXiv można znaleźć wyraźne uwagi „ten dokument został wycofany” na arXiv. Jestem prawie pewien, że jest więcej wycofanych dowodów niż tylko dokumenty arXiv z wyraźnym powiadomieniem. OK, wiem, że wycofanych dowodów nie należy zawyżać, ponieważ wycofanie „wcześniejszej próby potwierdzenia” nie oznacza, że ​​ci sami autorzy nie spróbują później. Ale milczenie o wycofanych próbach dowodowych wciąż wywołuje stronnicze wrażenie.
Thomas Klimpel
@ thomas niewielu „zwariowanych” autorów „wycofuje” swoje prace. niewypowiedzianym punktem listy woegorgi jest to, że ma wyraźnie niższą jakość niż papiery ARXIV. ale zgodziłem się, że woegorgi może dodać dodatkowe informacje i że może być nieco bardziej elastyczny w jego edycji. na przykład nie umieścił mojego konturu P vs NP na liście nawet po wysłaniu do niego e-maila, chociaż ostatnio opublikował inny element na dowodzie fukuyama związany z długim czatem na cstheory.se.
vzn
1
Doceniam to, że ponownie to odwiedzasz! Wygląda na to, że przecież przedwcześnie spodziewałem się nagrody dla niewłaściwej osoby. ;) Pamiętaj, że możesz użyć stackedit.io do przygotowania posta w miarę upływu czasu. Czekamy na resztę postu!
Raphael
34

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

ABPA=NPAPBNPB

PNPOPONPOA

P=?NP

Ran G.
źródło
1
Aby całkowicie poprawić, tutaj diagonalizacja oznacza bezpośrednią prostą diagonalizację. Zobacz to pytanie
Kaveh
1
Czyli relatywizacja nie jest techniką dowodową, ale efektem, który łamie dowód? Czy możesz podać / link do przykładu dowodu, który można relatywizować?
Raphael
2
tak, relatywizacja nie jest techniką dowodową, jest właściwością dowodu (nie ma tu formalnego charakteru). jeśli dowód działa bez zmian, gdy wszystkie maszyny Turinga są zastąpione maszynami wyroczni, wówczas dowód relatywizuje się. na przykład można przekonać się, że dowód twierdzenia o hierarchii czasu relatywizuje się w tym sensie.
Sasho Nikolov,
10

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. nk
  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?
Kaveh
źródło
7
Pytanie dotyczy „podejść, które okazały się nieskuteczne” oraz podejść „z historią upadków”, a odpowiedź ta nie wspomina o żadnym podejściu.
Tsuyoshi Ito
6
Chodzi mi o to, że ponieważ post na blogu w ogóle nie odpowiada na pytanie, nie ma sensu go kopiować i wklejać.
Tsuyoshi Ito
7
To naprawdę nie odpowiada na pytanie. Wpis na blogu to snarky lista kroków typowych dla P = NP? korba przechodzi. Podczas rozrywki nie dostarcza mi to konkretnych teorii , które wykazały, że nie są w stanie oddzielić (ani zwinąć) P i NP.
Raphael
4
Co powiesz na to? To pytanie wymaga barier dla udowodnienia P! = NP. Bariery w tej odpowiedzi (jak stwierdzono w komentarzach) to „zakładanie czegoś”, „zła interpretacja”, „mówienie, że coś jest jasne”, „wierzyć w coś”. Bariery te są zbyt ogólne, ponieważ stanowią przeszkody w udowadnianiu czegokolwiek, a nie konkretnie przeszkody w udowadnianiu P! = NP.
Tyson Williams
1
w komentarzach, mimo że są ważne, brakuje podstawowego punktu. blog został napisany przez lance fortnow, eksperta od teorii złożoności i światowego autorytetu w tej dziedzinie; właśnie wyszedł z nową książką o P vs NP Golden Ticket . więc mówi w zasadzie z własnego doświadczenia.
vzn
2

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

Ω(n2)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.

vzn
źródło
2
Nie rozumiem, jak to odpowiada na pytanie „jak nie udowodnić P? = NP”. W tej chwili wydaje się to raczej spekulacją na temat czyichś myśli.
Juho
2
Jasne, proponuję tylko wyjaśnić to wszystko. Złożoność obwodu nie jest nawet materiałem na poziomie licencjackim, więc pewne tło jest uzasadnione. Można oczekiwać, że czytelnik nie będzie ekspertem w teorii złożoności.
Juho,
@juho ok. kiedy raz zobaczyłem książkę Savage [która jest bardzo „obwodowo-centryczna”] używaną na poziomie licencjackim, również mnie zaskoczyło. uzgodniła swój zaawansowany materiał, stąd sformułowanie zdania pierwszego. jeśli chodzi o „spekulacje na temat myśli”, nie ma żadnej, oprócz cytowania własnych myśli Razborova zapisanych / zapisanych we własnych dokumentach.
vzn
1
a tak przy okazji, ogólnie jest to bardzo zaawansowane pytanie (niezupełnie na poziomie licencjackim), a inne odpowiedzi są zaawansowane i ogólnie poza poziomem licencjackim.
dniu