Konsekwencje nie do udowodnienia

Czytałem „ Czy P w porównaniu z NP jest formalnie niezależny? ”, Ale mnie to zaskoczyło.

Uważa się, że w teorii złożoności . Moje pytanie dotyczy tego, co jeśli nie da się tego udowodnić (powiedzmy w Z F C ). (Załóżmy, że dowiadujemy się tylko, że P ≠ N P jest niezależny od Z F C, ale nie ma dalszych informacji na temat tego, jak to udowodniono.)$\mathsf{P} \neq \mathsf{NP}$$ZFC$$\mathsf{P} \neq \mathsf{NP}$$ZFC$

Jakie będą konsekwencje tego stwierdzenia? Dokładniej,

twardość

Zakładając, że Uwiecznianie skutecznych algorytmów ( Cobham-Edmonds praca ) i P ≠ N P , to okazać N P - h R d n e s e wyniki sugerować, że są one poza zasięgiem niniejszego naszych skutecznych algorytmów. Jeśli okazać oddzielenie, N P - h o r d n e s s oznacza, że nie ma czasu algorytm wielomianem. Ale co robi N P - h a r d $\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP\text{-}hardness }$$\mathsf{NP\text{-}hardness}$ spowodować średnie czy separacja nie jest udowodnić? Co stanie się z tymi wynikami?$\mathsf{NP\text{-}hardness }$

wydajne algorytmy

Czy brak możliwości udowodnienia separacji oznacza, że ​​musimy zmienić naszą definicję wydajnych algorytmów?

Twoje pytanie może być lepiej sformułowane: „W jaki sposób na wpływ na teorię złożoności miałoby odkrycie dowodu, że P = NP jest formalnie niezależny od jakiegoś silnego systemu aksomatycznego?”

Trochę trudno jest odpowiedzieć na to pytanie w sposób abstrakcyjny, tj. Przy braku dostrzeżenia szczegółów dowodu. Jak wspomina Aaronson w swoim artykule, udowodnienie niezależności P = NP wymagałoby radykalnie nowych pomysłów, nie tylko na temat teorii złożoności, ale także na temat tego, jak udowodnić twierdzenia o niezależności. Jak możemy przewidzieć konsekwencje radykalnego przełomu, którego kształtu nie możemy obecnie nawet odgadnąć?

Mimo to możemy poczynić kilka spostrzeżeń. W następstwie dowodu na niezależność hipotezy kontinuum od ZFC (a później od dużych kardynałów ZFC +), znaczna liczba ludzi doszła do wniosku, że hipoteza kontinuum nie jest ani prawdziwa, ani fałszywa . Możemy zapytać, czy ludzie podobnie dojdą do wniosku, że P = NP nie jest „ani prawdą, ani fałszem” po dowodzie niezależności (dla celów argumentu załóżmy, że P = NP jest niezależny od ZFC + jakikolwiek duży aksjomat kardynalny). Nie sądzę. Aaronson w zasadzie mówi, że nie zrobiłby tego. Drugie twierdzenie Goedela o niekompletności nie skłoniło nikogo, kogo znam, do argumentowania, że ​​„ZFC jest spójny” nie jest ani prawdą, ani fałszem.i większość ludzi ma silną intuicję, że twierdzenia arytmetyczne - lub przynajmniej tak proste, jak „P = NP” - muszą być prawdziwe lub fałszywe. Dowód niezależności można interpretować po prostu jako stwierdzenie, że nie mamy możliwości ustalenia, które z P = NP a P $\ne$ NP ma miejsce.

Można również zapytać, czy ludzie interpretują ten stan rzeczy, mówiąc nam, że coś jest „nie tak” z naszymi definicjami P i NP. Być może powinniśmy zatem powtórzyć podstawy teorii złożoności za pomocą nowych definicji, z którymi łatwiej jest pracować? W tym momencie myślę, że jesteśmy w sferze dzikiej i bezowocnej spekulacji, w której próbujemy przekraczać mosty, do których jeszcze nie dotarliśmy i próbujemy naprawić rzeczy, które jeszcze się nie zepsuły. Co więcej, nie jest nawet jasne, czy cokolwiek by to zrobiłobyć „zepsuty” w tym scenariuszu. Teoretycy zestawów są całkowicie szczęśliwi, zakładając, że wszelkie duże aksjomaty kardynalne będą dla nich wygodne. Podobnie teoretycy złożoności mogą również, w tym hipotetycznym przyszłym świecie, być całkowicie szczęśliwi, zakładając, że wszelkie aksjomaty separacji, które ich zdaniem są prawdziwe, nawet jeśli są możliwe do udowodnienia.

Krótko mówiąc, nic nie wynika logicznie z dowodu niezależności P = NP. Oblicze teorii złożoności może się radykalnie zmienić w świetle tak fantastycznego przełomu, ale musimy tylko poczekać i zobaczyć, jak wygląda przełom.

To ważne pytanie, choć może trochę niestety sformułowane. Najlepsza odpowiedź, jaką mogę udzielić, to następujące odniesienie:

Scott Aaronson: Czy P kontra NP jest formalnie niezależny . Biuletyn Europejskiego Stowarzyszenia Teoretycznej Informatyki, 2003, vol. 81, strony 109–136.

Streszczenie: To jest ankieta na temat pytania tytułowego, napisana dla osób, które (jak autor) postrzegają logikę jako zabraniającą, ezoteryczną i daleką od zwykłych obaw. Począwszy od kursu zderzeniowego dotyczącego teorii Zermelo Fraenkela, omawia niezależność wyroczni; naturalne dowody; wyniki niezależności Razborowa, Raza, DeMillo-Liptona, Sazanowa i innych; oraz przeszkody w udowodnieniu P vs. NP niezależnie od silnych teorii logicznych. Kończy się rozważaniami filozoficznymi na temat tego, kiedy należy spodziewać się, że matematyczne pytanie będzie miało jednoznaczną odpowiedź.

$[ZFC][1]$ teorii. Oznacza to po prostu, że teoria nie może udowodnić ani twierdzenia, ani jego negacji. Nie oznacza to, że stwierdzenie nie ma wartości prawdziwości, nie oznacza, że ​​nie możemy poznać wartości prawdziwości stwierdzenia, możemy być w stanie dodać nowe rozsądne aksjomaty, które uczynią teorię wystarczająco silną, aby była w stanie udowodnić twierdzenia lub ich negację. Ostatecznie sprawdzalność w teorii jest formalną koncepcją abstrakcyjną. Jest to związane z naszym doświadczeniem w świecie rzeczywistym tylko jako model.

$\mathsf{P}$ . Zobacz ten post .

$\Sigma_1$$\Pi_1$Topologia przez logikę ”, 1996.)

$\mathsf{P} \neq \mathsf{NP}$$\Sigma_2$ to pytanie MO i przeszukać posty na liście mailingowej FOM .

Jak udowodniono w tym artykule:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf

Jeśli można wykazać, że P! = NP jest niezależny od arytmetyki Peano, wówczas NP ma ekstremalnie bliskie wielomianowi deterministyczne górne granice czasu. W szczególności w takim przypadku istnieje algorytm DTIME (n ^ 1og * (n)), który poprawnie oblicza SAT w nieskończenie wielu ogromnych przedziałach długości wejściowych.

Tylko kilka rozmyślań na ten temat. Nie krępuj się krytykować.

Niech Q = [nie można udowodnić (P = NP) i nie można udowodnić (P / = NP)]. Załóżmy, że Q jest sprzecznością. Zakładam również, że wszystkie znane odkrycia dotyczące P vs NP są nadal wykonalne. W szczególności wszystkie problemy NP są równoważne w tym sensie, że jeśli możesz rozwiązać jeden z nich w czasie wielomianowym, możesz rozwiązać wszystkie inne w czasie wielomianowym. Więc niech W będzie NP całkowitym problemem; W w równym stopniu reprezentuje wszystkie problemy w NP. Z powodu Q nie można uzyskać algotytydu A do rozwiązania W w czasie wielomianowym. W przeciwnym razie mamy dowód, że P = NP, co jest sprzeczne z Q (1) (*). Zauważ, że wszystkie algorytmy są obliczalne z definicji. Zatem powiedzenie, że A nie może istnieć, oznacza, że ​​nie ma sposobu na obliczenie W w czasie wielomianowym. Jest to jednak sprzeczne z Q (2). Pozostaje nam odrzucenie albo (1) xor, albo odrzucenie (2). Każdy przypadek prowadzi do kompromisu. Zatem Q jest sprzecznością,

(*) Możesz powiedzieć: „Aha! A może istnieć, ale po prostu nie możemy go znaleźć”. Cóż, jeśli A istniał, możemy wyliczyć wszystkie programy, aby znaleźć A, wyliczając od mniejszych programów do większych programów, zaczynając od pustego programu. Musi być skończony, ponieważ jest algorytmem, więc jeśli A istnieje, to program wyliczający, aby go znaleźć, musi zakończyć się.