Czy udowodnienie P ≠ NP byłoby trudniejsze niż udowodnienie P = NP?

Rozważ dwie możliwości problemu P vs. NP: P = NP i P $\neq$ NP.

Niech Q będzie jednym ze znanych problemów trudnych dla NP. Aby udowodnić P = NP, musimy zaprojektować pojedynczy algorytm wielomianowy A dla Q i udowodnić, że A poprawnie rozwiązuje Q.

Aby udowodnić P $\neq$ NP, musimy pokazać, że żaden algorytm czasu wielomianowego nie rozwiązuje Q. Innymi słowy, musimy wykluczyć wszystkie algorytmy czasu wielomianowego.

Słyszałem, jak ludzie mówią, że to drugie zadanie jest trudniejsze (zakładając, że to naprawdę prawda).

Czy istnieje powód, by sądzić, że udowodnienie P = NP (przy założeniu, że P = NP) byłoby łatwiejsze niż udowodnienie P $\neq$ NP (przy założeniu, że P $\neq$ NP)?

Jak wyjaśnia Raphael, pytanie to jest źle postawione, ponieważ co najwyżej jedno z P = NP i P ≠ NP powinno być w ogóle możliwe do udowodnienia. Jednak podobne pytanie pojawia się w informatyce teoretycznej w kilku postaciach, z których najbardziej widoczna jest w dziedzinie algorytmów aproksymacyjnych .

Biorąc pod uwagę trudny do optymalizacji NP problem (powiedzmy, maksymalizacja), możemy zapytać, jak dobrze możemy go przybliżyć. Udowodnienie górnej granicy możliwego przybliżenia jest podobne do P = NP, podczas gdy udowodnienie dolnej granicy możliwego przybliżenia jest podobne do P ≠ NP. Ten pierwszy jest znacznie łatwiejszy niż drugi. Rzeczywiście, aby udowodnić górną granicę, wystarczy wymyślić algorytm aproksymacyjny i go przeanalizować. Natomiast wszystkie znane dolne granice są warunkowe: są ważne tylko wtedy, gdy P ≠ NP (rzeczywiście, jeśli P = NP, wówczas każdy problem optymalizacji NP-trudnej stałby się rozwiązaniem). Aby udowodnić te dolne granice, pokazujemy, że jeśli moglibyśmy zbyt dobrze przybliżyć problem, uzyskalibyśmy algorytm wielomianowy czasu dla jakiegoś trudnego NP. Zwykle odbywa się to za pomocą skomplikowanej techniki technicznej twierdzenia PCP. Do tego obszaru, znanego jako twardość aproksymacji , można podchodzić wyłącznie przez specjalistów i jest technicznie trudniejszy niż większość algorytmów aproksymacyjnych. Zatem przynajmniej w tym przypadku P = NP jest rzeczywiście łatwiejsze niż P ≠ NP.

Nie wykluczyliśmy możliwości prostego dowodu, że P = NP. Jeśli ktoś jutro wymyśli algorytm, który rozwiązuje problem NP-zupełności w czasie P, świat się zmienia.

Z drugiej strony, nie wykluczył możliwość prostego dowodu, że P = NP!. Nasze typowe techniki dowodowe pokazujące, że dwie różne klasy złożoności okazały się formalnie niewystarczające. Trzy takie techniki są znane jako „arytmetyzacja”, „dowód naturalny”, a kategoria dowodów nazywana „relatywizacją” (te, które nie dbają o to, jakie wyrocznie są używane). Można udowodnić, że żadna technika dowodowa, która mieści się w którejkolwiek z 3 kategorii, nie może udowodnić P! = NP.

W rezultacie istnieją mocne dowody na to, że udowodnienie P! = NP wymaga nowego rodzaju dowodu (nowe techniki o różnych właściwościach), a nie tylko nowego zastosowania dobrze znanych technik dowodu.

Teraz może się okazać, że P = NP, podczas gdy nie ma łatwego do zweryfikowania algorytmu w P, który rozwiązuje problem NP-zupełny, i że do udowodnienia P = NP wymagane są nowe techniki dowodu. (Jeśli P = NP, znamy już algorytmy, które technicznie są w P, które zabawnie rozwiązują problemy NP-trudne. Nie są praktyczne do uruchomienia, ponieważ ich stały współczynnik jest duży.)

Zasadniczo wiemy dużo o tym, czego nie możemy użyć do udowodnienia P! = NP, podczas gdy pozornie wiemy niewiele o tym, czego nie możemy użyć do udowodnienia P = NP.

Cóż, w zasadzie masz pomysł. Generalnie uważamy, że P! = NP, ale nie mamy pojęcia, jak moglibyśmy udowodnić, że te rzeczy nie są równe.

I odwrotnie, jeśli P = NP, można by pomyśleć, że do tej pory znaleźlibyśmy algorytm, który rozwiązałby jeden z dziesiątek problemów związanych z NP-zupełnością.

Są to bardzo przekręcone argumenty, ale w kilku zdaniach opisują kulturę wśród informatyków.

To, czy udowodnienie, że P! = NP jest „trudniejsze”, zależy oczywiście od tego, co jest prawdziwe (z wyjątkiem wyników meta-matematycznych?) I tego oczywiście nie wiemy.

$\neq$$\land$$\lor$$\lnot$n $\mod_6$bramki, które nie potrafią rozwiązać SAT (w laika) jest możliwe, że istnieje algorytm równoległego stałego czasu z wielomianową liczbą procesorów, który rozwiązuje SAT i każdy proces oblicza tylko jedną z tych bramek. Najlepsze dolne granice, jakie mamy dla maszyn Turing rozwiązujących SAT, nie mogą nawet pokazać, że nie ma algorytmu, którego czas pracy pomnożony przez zajmowaną przez niego przestrzeń wynosi . Mogę sporo mówić o dość zawstydzającym stanie udowodnienia dolnych granic (pamiętaj jednak, że mamy również wyniki barier wyjaśniające, dlaczego tak trudno jest udowodnić dolne granice). Niektórzy eksperci uważają, że program GCT Ketana Mulmuleya jest najbardziej prawdopodobny do rozwiązania P vs. NP, a sam Mulmuley powtórzył, że jego zdaniem prawdopodobnie zajmie to ponad sto lat.$n^{1.9}$

Jednak ostatnio pojawiły się prace Ryana Williamsa i innych, które pokazują, że istnieją nieodłączne powiązania między udowadnianiem dolnych granic a wyszukiwaniem algorytmów. Np. Wykazał, że algorytm nieco lepszy niż algorytm brutalnej siły dla określonego ograniczonego problemu SAT implikuje dolne granice obwodu, a następnie zaprojektował taki algorytm. Myślę więc, że ludzie są nieco mniej pesymistyczni, a także nie wydają się rozwijać algorytmu i udowadniać, że dolne granice są tak odrębne, jak ludzie sądzili, że są.

Wróćmy teraz do pytania i spróbujmy spojrzeć na to nieco bardziej religijnie. Aby odpowiedzieć na pytanie, musimy sformalizować, co rozumiemy przez trudność udowodnienia stwierdzenia. W tym celu możemy wykorzystać teorię dowodu i złożoność dowodu, która dokładnie analizuje różne sposoby określania twardości dowodu stwierdzenia. Pozwólcie, że krótko wyjaśnię, na czym polega złożoność dowodu. System dowodów jest zasadniczo algorytmem weryfikującym dla dowodów. Dajemy ciąg i ciąg i pytamy, czy jest dowodemφ π $\pi$$\varphi$$\pi$$\varphi$a algorytm zwraca tak lub nie. W ten sposób możesz wymyślić dowolne narzędzie sprawdzające. Możesz także pomyśleć o dowodach w systemie matematycznym takim jak ZFC jako takim. Sam proces sprawdzania może być wykonywany w czasie wielomianowym o wielkości dowodu, ponieważ jest to zadanie składniowe.

Teraz rozważ formułę . Co to znaczy, że jest trudne do udowodnienia? Jedną z możliwości jest to, że najkrótszy dowód jest bardzo duży. Jeśli jest zbyt duży, powiedzmy, że liczba bitów wymaganych do jego przedstawienia jest większa niż wówczas nie możemy nawet podać dowodu. Drugą możliwością jest to, że dowód nie jest zbyt duży, ale trudno go znaleźć. Pozwól, że wyjaśnię to trochę: pomyśl o algorytmie wyszukiwania dowodu. Większość reguł jest deterministycznych w systemie takim jak LKφ φ 2 $\varphi$$\varphi$$\varphi$$2^{65536}$w tym sensie, że można ustalić poprzednie linie z bieżącej linii w dowodzie i regule. Ważnym wyjątkiem jest reguła cięcia. Jest to ważne, ponieważ chociaż nie potrzebujemy reguły cięcia do udowodnienia oświadczeń, może ona znacznie zmniejszyć rozmiar najkrótszego dowodu. Jednak zasada cięcia nie jest deterministyczna: istnieje formuła cięcia, którą musimy odgadnąć. Możesz myśleć o regule cięcia jako dowodzeniu lematów i używaniu ich. Formuła cięcia jest jak lemat. Ale jaki lemat powinniśmy udowodnić, że nam pomoże? To jest trudna część. Często wynik w matematyce jest udowodniony przez znalezienie dobrego lematu. Również, gdy używasz wcześniej sprawdzonych wyników, zasadniczo używasz reguły cięcia. Kolejnym ważnym elementem w dowodzeniu stwierdzeń są definicje. Często definiujemy nową koncepcję, a następnie potwierdzamy oświadczenia na jej temat, i na koniec zastosuj go w naszym szczególnym przypadku. Używanie definicji zmniejsza rozmiar formuł (spróbuj rozszerzyć formułę matematyczną do czysto ustawionego języka teoretycznego, rozszerzając definicje, aby zorientować się, jak ważne są definicje). Znowu jakich nowych definicji powinniśmy użyć? Nie wiemy To prowadzi mnie do trzeciego znaczenia stwierdzenia, które jest trudne do udowodnienia. Stwierdzenie może być trudne do udowodnienia, ponieważ potrzebujesz silnych aksjomatów. Weź np Stwierdzenie może być trudne do udowodnienia, ponieważ potrzebujesz silnych aksjomatów. Weź np Stwierdzenie może być trudne do udowodnienia, ponieważ potrzebujesz silnych aksjomatów. Weź npCH . Nie można tego udowodnić w ZFC ani nie można go obalić w ZFC. To skrajny przypadek, ale zdarza się to częściej, niż myślisz. Np. Czy potrzebujemy dużych kardynalnych aksjomatów (aby móc pracować we wszechświatach Grothendiecka ), aby udowodnić FLT, czy możemy udowodnić to w znacznie słabszej teorii, takiej jak PA ? To kolejna koncepcja dotycząca trudności w potwierdzaniu wypowiedzi.

Wróćmy teraz do P vs. NP. Nie mamy wyników wskazujących, że problemu nie da się rozwiązać w ten czy inny sposób w raczej słabych teoriach arytmetycznych. Alexander Razborov napisał w 1995 r. Artykuł zatytułowany „Niedopuszczalność dolnych granic wielkości obwodu w niektórych fragmentach ograniczonej arytmetyki”, który wykazał, że nie można tego udowodnić w jakiejś słabej teorii, ale teoria jest naprawdę bardzo słaba. Według mojej wiedzy nie poczyniono dużego postępu w rozszerzeniu tej teorii na znacznie silniejsze teorie, takie jak ograniczone teorie arytmetyczne Sama Bussa, a nawet jeśli wynik zostanie rozciągnięty na nich, nadal są daleko od czegoś takiego jak PA lub ZFC. Krótko mówiąc, nie tylko nie możemy udowodnić, że SAT nie jest w bardzo małych klasach złożoności, nie możemy nawet udowodnić, że nie możemy udowodnić P≠ ≠ $\neq$NP w bardzo słabych teoriach. Formalnym powodem, dla którego mamy trudności z udowodnieniem, że P NP jest bariera, można stwierdzić, że takie i takie techniki nie mogą same w sobie udowodnić, że P NP. Są to dobre wyniki, ale nawet nie wykluczają możliwości połączenia tych technik, aby pokazać P NP.$\neq$$\neq$$\neq$

Myślę, że pytanie można sprowadzić do: czy łatwiej jest udowodnić, że coś istnieje, czy udowodnić, że coś nie istnieje.

Argumentem przemawiającym za udowodnieniem, że coś istnieje, jest łatwość konstruowania rzeczy, które mogą spełniać wymagania, a także łatwe sprawdzenie, czy rzeczywiście je spełniają.

W niektórych przypadkach jest to prawdą: jeśli chcesz znaleźć pierwiastek wielomianu, łatwo jest skonstruować liczby i łatwo sprawdzić, czy są pierwiastkami.

Problem polega oczywiście na tym, że musisz mieć szczęście. Możesz zmniejszyć przestrzeń wyszukiwania, np. Udowadniając, że musi to być wielokrotność 5 lub od 1 do 10; ale jeśli nie ograniczysz go do skończonego zestawu liczb (w takim przypadku tak naprawdę nie używasz metody „zgadnij i sprawdź”), nie masz metody rozwiązania problemu: masz tylko metodę, która przy założeniu masz szczęście, może wygenerować rozwiązanie.

Ale jeśli tego chcesz, równie łatwo jest udowodnić, że coś nie istnieje! Wygeneruj teksty, które mogą być możliwymi rozwiązaniami, i sprawdź, czy rzeczywiście są.

Dlatego posiadanie metody, która może przynieść rozwiązanie przez szczęście, nie oznacza, że ​​udowodnienie, że coś istnieje, jest łatwiejsze.

Czy ogólnie łatwiej jest udowodnić, że coś istnieje za pomocą innej metody? Zależy to od rzeczywistego problemu, ponieważ w przeciwnym razie udowodnienie, że coś nie istnieje, sprowadzałoby się do udowodnienia, że ​​istnieje dowód, że nie istnieje. Obawiam się, że nie możemy tego zmierzyć, ponieważ nigdy nie było czegoś, co udowodniono, że istnieje i nie istnieje, więc możemy (próbować) zmierzyć trudność dowodu.

Jeśli udowodnisz, że P = NP, udowodnienie czegoś przeciwnego jest nie tylko trudniejsze, ale niemożliwe.

Uważam, że niemożliwe jest udowodnienie P <> NP, ponieważ musiałbyś wykluczyć wszystkie algorytmy, które mogłyby udowodnić P = NP. Możliwych może być nieskończona liczba. Nie ma sposobu obalenia nieskończoności, dlatego nie jest to możliwe. Z drugiej strony wystarczy jeden algorytm, aby udowodnić P = NP, jeśli tak jest. Dlatego albo P = NP, który ktoś udowodni, albo nigdy się nie dowiemy.