Konsekwencje nie do udowodnienia

22

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 ). (Załóżmy, że dowiadujemy się tylko, że jest niezależny od 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 , to okazać wyniki sugerować, że są one poza zasięgiem niniejszego naszych skutecznych algorytmów. Jeśli okazać oddzielenie, oznacza, że nie ma czasu algorytm wielomianem. Ale co robi $\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?

— karthik
źródło

13

Pierwszą rzeczą, o którą musisz zapytać, jest: formalnie niezależny od czego? W logice matematycznej istnieje wiele zestawów aksjomatów, które ludzie rozważali. Domyślną jest ZFC, czyli teoria mnogości Zermelo-Fraenkela z Axiom of Choice. Niezależność od ZFC oznacza, że ani P = NP, ani P! = NP nie mogą być udowodnione na podstawie tych aksjomatów.

— Peter Shor

2

Jeśli chcesz wiedzieć, jak wygląda dowód na stwierdzenie, że „czy X jest niezależny od systemu aksomatycznego Y”, dlaczego po prostu nie przeczytasz kilku przykładów? Niezależność aksjomatu wyboru od teorii zbiorów Zermelo-Fraenkela jest znanym przykładem. Głosowałem przez pomyłkę, że nie jest to prawdziwe pytanie przez pomyłkę, ale chciałem zagłosować za zamknięciem jako nie na temat.

— Tsuyoshi Ito

15

Czy przeczytałeś bardzo dobry i swobodnie dostępny artykuł Scotta Aaronsona; „Czy P kontra NP jest formalnie niezależny?” ( scottaaronson.com/papers/pnp.pdf )

— Marzio De Biasi

2

Pytanie „jeśli X zostanie udowodnione jako niezależne od ZFC, a mamy pewne twierdzenia o formie X

Y, co stanie się z tymi twierdzeniami?” wydaje się być dobrze postawiony i jest to pytanie, które, jak sądzę, zadaje OP. Odpowiedź wydaje się być następująca: w niektórych systemach aksjomatów, takich jak ZFC + X, mamy wtedy trzymanie Y, podczas gdy w ZFC +

X nie mamy informacji o Y. Jako takie, te twierdzenia warunkowe nadal miałyby pewną wartość. W rzeczywistości, oni mają większą wartość w tej sytuacji, niż gdyby

X miały być okazało się twierdzenie.

\to

$\rightarrow$

\neg

$\lnot$

\neg

$\lnot$

— András Salamon,

2

Niedopuszczalność PFC w porównaniu z NP miałaby prawdopodobnie znacznie więcej implikacji dla teorii mnogości niż teorii złożoności.

— David Harris

18

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.

— Timothy Chow
źródło

3

@vzn: Twoje przykłady nie są po prostu „prawdopodobnie” arytmetyczne; są niewątpliwie arytmetyczne. Ale nie jestem pewien, o co ci chodzi. Weźmy równanie

diofantyny z właściwością, że „

nie ma rozwiązań” jest nierozstrzygalne w ZFC. Chodzi mi o to, że każdy, kogo znam, wierzy, że albo

ma rozwiązania, albo nie, i że nie możemy tego udowodnić w ten czy inny sposób. Czy wierzysz, że nie ma znaczenia, czy

ma rozwiązania - że

nie ma ani nie ma rozwiązań?

E

$E$

E

$E$

E

$E$

E

$E$

E

$E$

— Timothy Chow,

4

@vzn: Myślę, że całkowicie nie rozumiesz sedna sprawy. Pytanie nie dotyczy tego, czy dane stwierdzenie jest nierozstrzygalne , ale czy nie jest ani prawdziwe, ani fałszywe . Te dwie koncepcje są całkowicie odmienne. Czy powiedziałbyś na przykład, że ZFC nie jest ani spójny, ani niespójny? Wszyscy (inni), których znam, są przekonani, że albo ZFC jest spójny, albo nie, nawet jeśli nie mamy możliwości ustalenia, co się dzieje.

— Timothy Chow

3

„Dla mnie to brzmi jak religia, a nie matematyka” - Witamy w metamatematyce. Być może mniej kontrowersyjnym sposobem powiedzenia „X nie jest ani prawdą ani fałszem” jest to, że nie mamy a priori powodu, aby preferować system aksjomatyczny, w którym X jest prawdziwy, niż system aksomatyczny, w którym X jest fałszywy. Mamy (prawie) powszechnie uzgodniony standardowy model arytmetyczny; jako konwencja społeczna akceptujemy wyrażenia arytmetyczne, które utrzymują się w tym modelu, jako prawdziwe, faktycznie prawdziwe. Tego samego nie można powiedzieć o teorii mnogości.

— Jeffε

2

Zobacz także consc.net/notes/continuum.html i mathoverflow.net/questions/14338/... - Osobista mieszanka formalizmu, platonizmu i intuicjonizmu każdego matematyka jest zasadniczo przekonaniem religijnym.

— Jeffε

2

@vzn: Wciąż brakuje ci sensu. Nawet jeśli udzielimy ci twoich osobistych przekonań religijnych, mówisz tylko, że nie dołączysz do Aaronsona i reszty świata w oświadczeniu, że zdania arytmetyczne są prawdziwe lub fałszywe. Wszyscy zgadzają się, że nie ma sposobu, aby powiedzieć z formularza oświadczenia, czy jest nierozstrzygalny , ale nie jest to twierdzenie. Twierdzenie to, że prawie wszyscy oprócz ciebie nie mają silne intuicje że arytmetyczne stwierdzenia są prawdziwe lub fałszywe . To, że nie podzielasz tego przekonania, nie oznacza, że inni go nie mają.

— Timothy Chow,

11

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

— Andrej Bauer
źródło

2

Uh, całkowicie przegapiłem fakt, że artykuł Aaronsona był już wspomniany w komentarzach. Przepraszam.

— Andrej Bauer

7

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

— Kaveh
źródło

4

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.

— Istotny
źródło

0

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

— Thomas Eding
źródło

1

@Victor: Dobra uwaga. Wyobrażam sobie, że jeśli A istnieje, to można po prostu przeanalizować każdy wyliczony program, aby sprawdzić, czy rzeczywiście rozwiązuje on NP całkowity problem w czasie wielomianowym. Uważam, że skoro ktoś pracuje ze skończonym zestawem instrukcji (podanym przez jakiś uniwersalny komputer), można rozpoznać A Ale nie jestem ekspertem.

— Thomas Eding,

1

Problem polega na tym, że jeśli Q jest prawdziwe, to wpadlibyśmy w przypadek, w którym nikt, bez względu na to, jak inteligentny jest, nie mógłby udowodnić, że określony algorytm X wygenerowany przez moduł wyliczający rozwiązuje P = NP, nawet jeśli tak jest. To znaczy w tym przypadku algorytm służący do ustalenia, czy P = NP istnieje i można go znaleźć, ale niemożliwe jest analityczne udowodnienie jego poprawności. Dalej stwierdzenie typu „czy algorytm X rozwiązuje problem P = NP?” brzmi bardzo nierozstrzygalnie.

— Victor Stafusa,

1

Także ... Jeśli A istnieje, to niech N będzie wielkości A. Niech T będzie zbiorem wszystkich programów o rozmiarze <= N. Można jednocześnie uruchomić W na wszystkich A 'w T. Gdy każde A' zakończy się, uruchom wyjście O za pomocą programu, który sprawdza, czy O rozwiązuje W. (Należy zauważyć, że każde tak zwane „rozwiązanie” problemu NP zupełnego można zweryfikować w czasie wielomianowym.) Jeśli O jest poprawną odpowiedzią, wyłącz wszystkie inne komputery i zwróć O. Należy pamiętać, że nie każde A 'musi zakończyć się, ponieważ A jest jednym z nich i wyświetli prawidłowe O w czasie wielomianowym. Zatem nie trzeba nawet udowadniać, że A rozwiązuje P = NP. N istnieje z definicji.

— Thomas Eding

1

W sekcji (*): „A musi być skończony, ponieważ jest algorytmem, więc jeśli A istnieje, to program do wyliczania, aby go znaleźć, musi zakończyć się.”. Oznacza to, że moduł wyliczający powinien w jakiś sposób być w stanie ustalić, czy program, który właśnie wygenerował, rozwiązuje problem NP-zupełny w czasie wielomianowym, co z pewnością jest nierozstrzygalne (tym bardziej, że zakładamy tutaj Q), a zatem moduł wyliczający nigdy się nie zatrzyma .

— Victor Stafusa,

3

„P = NP jest niezależny od ZFC” nie jest tym samym, co „nie możemy znaleźć algorytmu, który rozwiązałby jakikolwiek problem w NP w deterministycznym czasie wielomianowym”, jak wskazał Victor. Dokładne definicje tych klas są raczej ważne w przypadku takich pojęć, jak niezależność w odniesieniu do teorii.

— András Salamon,