Jeśli wszyscy wierzą w P ≠ NP, dlaczego wszyscy sceptycznie podchodzą do prób udowodnienia P ≠ NP?

55

Wielu wydaje się wierzyć, że , ale wielu uważa również, że jest bardzo mało prawdopodobne, aby kiedykolwiek to udowodniono. Czy nie ma w tym żadnej niespójności? Jeśli uważasz, że taki dowód jest mało prawdopodobny, powinieneś również uwierzyć, że brakuje solidnych argumentów za Czy też istnieją dobre argumenty za tym, że jest mało prawdopodobne, podobnie jak w powiedzeniu, hipoteza Riemanna o dużych liczbach lub bardzo wysokie dolne granice liczby istniejących liczb pierwszych o małej odległości od siebie. hipoteza Twin Prime? $P\ne NP$ $P\ne NP$ $P\ne NP$

complexity-theory p-vs-np

— pafnuti
źródło

61

Ponieważ pobożne życzenia nie dają dowodów. A ponieważ to nie wszyscy. A ponieważ „uwierzenie” nie wystarcza większości matematycznie myślących ludzi.

— Raphael

26

„dlaczego wszyscy są sceptycznie nastawieni do prób dowodowych” jest czymś zupełnie innym niż „wielu uważa, że jest bardzo mało prawdopodobne, aby to kiedykolwiek zostało udowodnione”.

— Tom van der Zanden,

95

Wierzę w istnienie prezydenta Nigerii i że czasami napotyka on problemy związane z przenoszeniem waluty. Jednak jestem sceptyczny wobec otrzymywanych przeze mnie wiadomości e-mail z prośbą o pomoc w rozwiązaniu tych problemów.

— Gilles „SO- przestań być zły”

3

w tym momencie problem został otwarty prawie półtora wieku i istnieje nieodebrana nagroda w wysokości 1 miliona dolarów od ponad półtorej dekady (Claymath). problem jest więc prawdopodobnie mniej więcej tak samo trudny jak i epickie, jak te, o których wspomniałeś (liczby pierwsze Riemanna / Twin). Riemann pozostaje nierozwiązany przez ~ 1½ wieku, a bliźniacze liczby pierwsze wciąż pozostają nierozwiązane po ~ 2 Millenii. innymi słowy ogólny konsensus / konwencjonalna mądrość brzmi „wydaje się być prawdą”, ale „z powodów, które wykraczają poza obecne ludzkie rozumienie / istniejące techniki matematyczne / wiedzę”. Jednak większość naukowców wierzy, że będzie w końcu zostać rozwiązane ...

— vzn

3

Wygląda na to, że wszyscy skupili się na uzasadnieniu powodów, dla których sceptycznie podchodzili do nowych prób próby ... ale nikt tak naprawdę nie odniósł się do tego, co moim zdaniem było głównym pytaniem PO: dlaczego / jak jesteśmy tak pewni, że coś, co wydaje się nie do udowodnienia, jest nadal prawdopodobne ? jako kompletny laik idiota wydaje mi się analogiczne do tego, że trudniej jest udowodnić, że coś nie istnieje niż coś istnieje (jeśli coś masz, to drugie jest łatwe, ale dla pierwszego nigdy nie masz pewności, czy to naprawdę nie istnieje lub po prostu go jeszcze nie znalazłeś)

— Anentropic,

94

Ludzie są sceptyczni, ponieważ:

Nie ma żadnego dowodu od eksperta, który nie został później unieważniony
Tak wiele wysiłku włożono w znalezienie dowodu, bez powodzenia, że zakłada się, że albo będzie on znacznie skomplikowany, albo wymyślisz nową matematykę dla dowodu
Pojawiające się „dowody” często nie uwzględniają przeszkód, o których wiadomo, że istnieją. Na przykład wielu twierdzi, że 3SAT nie znajduje się w P, podając argument, który dotyczy również 2SAT.

Dla jasności sceptycyzm dotyczy dowodów, a nie samego rezultatu.

— jmite
źródło

16

Ważną kwestią jest to, że wykazano, że szerokie klasy technik dowodowych nie są wystarczające. Zobacz edycję Wikipedii : wspomniano również w odpowiedzi

— Evila

4

Innym powodem, który uważam za ważny, jest powaga sytuacji, jeśli ktoś źle zrozumie odpowiedź. Jeśli ktoś przyjmie P ≠ NP, a to okaże się fałszywe, istnieje infrastruktura i transakcje o wartości miliardów dolarów, które są przede wszystkim chronione przez przypuszczalny charakter ataku NP na ich kryptografię.

— Cort Ammon,

14

@CortAmmon Ale odkrywanie deterministyczny

algorytmy do tych problemów, prawdopodobnie nie miałoby żadnego praktycznego znaczenia.

Θ (n^{100})

$\Theta(n^{100})$

— David Richerby,

@DavidRicherby - z drugiej strony, przynajmniej z łamania algorytmów kryptograficznych złożoność często pochodzi zasadniczo z upływem czasu.

— TLW

@TLW Przepraszam, byłem nieprecyzyjny. Miałem na myśli, że nie miałoby to większego znaczenia dla kryptografii, gdybyśmy odkryli, że problemy w NP mają algorytmy czasu wielomianowego, ale że każdy taki algorytm ma czas działania

. W takim przypadku nie ma możliwości poprawy.

Ω (n^{100})

$\Omega(n^{100})$

— David Richerby

44

Wiara jest prostopadła do dowodów. Wiara może kierować próbami rozwiązania przez badaczy, a raczej ich głównym zainteresowaniem, ale to i tak nie uniemożliwia im sprawdzenia dowodów.

Problem z polegający na tym, że wiele standardowych sposobów próby udowodnienia jest już wykluczonych jako niewystarczające, aby cokolwiek wywnioskować, patrz tutaj po dalsze szczegóły. $P \ne NP$

Nie ma niespójności w zebranych badaniach podejrzeń i wykształconych przypuszczeń. Również przekonanie, że coś nie zostanie udowodnione, nie jest w żaden sposób wnikliwe, bez dowodu na to, że nie można tego udowodnić.

Lata prób, roszczeń i odrzuconych metod czynią ludzi sceptycznymi.

Proszę spojrzeć na wcześniejsze artykuły, które próbowały przyczynić się do rozwiązania.

„Roszczenia nadzwyczajne wymagają nadzwyczajnych dowodów”.

To dość dokładnie charakteryzuje sceptycyzm.

— Zło
źródło

7

Cóż, nie ortogonalny . Wyraźne udowodnienie prawdziwości jest skorelowane z przekonaniem, że jest prawdą.

— Accumumulation

2

Czy Twój wyróżniony cytat nie mówi o tym, co zadaje oryginalne pytanie? Tj. Jeśli stwierdzenie P ≠ NP jest tak powszechnie uważane i akceptowane, to dlaczego jest to roszczenie nadzwyczajne, czy nie powinno być zwykłym roszczeniem? Chyba tak, jak mówisz, niezwykłe twierdzenie nie polega na tym, że P ≠ NP, ale na znalezieniu dowodu. Byłoby to nadzwyczajne na podstawie historii próbnych dowodów. Nie jestem pewien, o co mi chodzi, poza tym, że twój nacisk na ten cytat był interesujący. :)

— Jack Casey,

3

Jeśli używasz słowa „ortogonalny”, co oznacza coś innego niż „nieskorelowany”, to myślę, że używasz tego w niestandardowy sposób.

— Accumumulation

1

Używam słowa „ortogonalny” w najbardziej standardowy i zgodny z cs / matematyki / dsp sposób i nie zgadzam się z korelacją, biorąc pod uwagę standardowy MO, a nawet podałem przykład. Nie jest on skorelowany z naukowego punktu widzenia, ale z heurystyki behawioralnej, której nie należy mieszać.

— Zły

1

@JackCasey, roszczenie jest nadzwyczajne, ponieważ nie zostało udowodnione, w porównaniu do tysięcy innych udowodnionych roszczeń. Nie ma znaczenia, że wszyscy tak „wierzą”.

— Arturo Torres Sánchez

22

Kilka powodów, niektóre ogólne i niektóre szczegółowe.

Ogólny powód jest taki, że jest to znany od dawna znany problem, który wielu inteligentnych ludzi próbowało rozwiązać, a wielu inteligentnych ludzi się myliło. Szanse, że jakikolwiek nowy dowód jest ważny, są bardzo niskie w oparciu o tę historię.

W tym konkretnym przypadku przeprowadzono badania nad tym, które dowody nie działają . Wykazano, że w zasadzie wszystkie znane techniki dowodowe do udowodnienia rzeczy w informatyce nie mogą udowodnić P! = NP .

Wikipedia obejmuje to i wskazuje, w jaki sposób „relatywizujące dowody” (dowody, które działają niezależnie od tego, do czego wyroki ma twoja TM), „dowody naturalne” (obejmujące dolne granice obwodu) i „arytmetyzacja” są albo niewystarczające, aby odróżnić P i NP (pokaż, że są równe lub różne), lub jakikolwiek taki dowód byłby absurdalnie silniejszym wynikiem.

Krótko mówiąc, nie tylko wielu inteligentnych ludzi pracowało przez tak długi czas i poniosło porażkę, ale po tym, jak udowodnili, że całe rodziny dowodów nie mogą być wykorzystane do rozwiązania tego problemu. Kiedy więc ktoś wymyśli P! = NP, pojawia się naturalny sceptycyzm, po którym następuje zauważenie, że jeden z wielu dowodów na temat takich dowodów został naruszony, a wtedy nie ma już potrzeby sprawdzania reszty wyniku.

— Jak
źródło

Zastanawiam się, czy to prawda, że wielu inteligentnych ludzi próbowało udowodnić P P NP, czy też skupili się na czymś osiągalnym, na przykład pokazując, że pewne znane techniki dowodowe nie działają.

— gnasher729,

3

@gnasher Przeczytaj wikipedię. Te dowody „ta technika nie może działać” wypłynęły z prób użycia tych technik do udowodnienia, że P? = NP. Każdy, kto wymyśli niewiarygodny dowód na wszystko w CS, który nie podlega innym wykluczonym technikom dowodzenia, założycie się, że ludzie go wypróbują.

— Yakk,

Dolna granica ACC0 od Ryana Williamsa pozornie omija wszystkie znane bariery (jeśli istnieją dla obwodów ACC0).

— Lwins

7

Ludzie nie wierzą w żadne „dowody” z powodu postrzeganej trudności.

Powiedzmy, że spotykamy kosmitów, którzy są lepsi w matematyce niż ludzie. Ich średnie dziecko w wieku szkolnym jest tak samo dobre w matematyce, jak nasi najwięksi matematycy. Nie inteligentne dziecko w wieku szkolnym, ale przeciętne dziecko w wieku szkolnym.

Udowodnili hipotezę Riemanna, twierdzenie o podwójnej prymacie i pierwszą hipotezę Hardy'ego-Littlewooda oraz hipotezę Goldbacha. Co sądzą o udowodnieniu, że problem Podróżującego sprzedawcy można rozwiązać w czasie wielomianowym? Przekonają się, że jest mało prawdopodobne, aby ktokolwiek mógł to rozwiązać. Co myślą o udowodnieniu, że problemu Traveling Salesman nie da się rozwiązać w czasie wielomianowym? Myślę, że jeszcze mniej prawdopodobne będzie, że ktoś znajdzie dowód.

To tylko moja opinia, ale jeśli ktoś powie, że ma dowód na P = NP lub P ≠ NP, nie uwierzę.

PS. Hipoteza Riemanna jest otwarta na dłużej, ponieważ jest to klasyczny problem matematyczny, który miał sens dla matematyków 100 lat temu. P ≠ NP to informatyka, coś znacznie nowszego, a AFAIK całe pojęcie NP pochodzi tylko z lat siedemdziesiątych. Nastąpił postęp w hipotezie Riemanna (nie możemy udowodnić „wszystkie zera yada yada”, ale przynajmniej „duża część wszystkich zer yada yada”), w przeciwieństwie do P ≠ NP. Jest jednowymiarowy. Chodzi o zera jednej funkcji. P ≠ NP dotyczy wszystkich możliwych algorytmów rozwiązania problemu.

— gnasher729
źródło

7

Jak myślisz, dlaczego rozwiązanie P vs NP jest trudniejsze niż, powiedzmy, hipoteza Riemanna? Ten ostatni jest otwarty o wiele dłużej.

— Yuval Filmus,

4

Nie spekuluję na temat tego, co kosmici, którzy są mądrzejsi od nas, mogliby uznać za niefaktyczne opinie, które są przydatne.

— Mateusz

1

Nie ma korelacji między trudnością a wiekiem problemów matematycznych. Nie ma unikalnego rozwiązania problemu matematycznego. Trudność zależy od perspektywy. Mogą istnieć proste rozwiązania P = NP, a także mogą być złożone, podobnie jak w przypadku Hipotezy Riemanna i innych hipotez. Wreszcie stwierdzenie, że RH dotyczy zer jednej funkcji i dlatego nie jest tak trudne, nie jest poprawne. Wiele trudnych problemów matematycznych można przeformułować jako zera funkcji.

— Glen Wheeler

1

@GlenWheeler Jak zdefiniować trudność bez odwoływania się do tego, jak ciężko pracują ludzie, aby ją rozwiązać, co koniecznie wywołuje, jak długo problem był dostępny?

— djechlin

Trudność to problematyczna koncepcja. Zamiast używać takiego niepoprawnie zdefiniowanego języka, zamiast tego mów o tym, co naprawdę masz na myśli: np. Że istnieje już od X lat, z których Y jest jednym ze słynnych „problemów z milionem dolarów”. To już wskazuje na to, co chcesz wyciągnąć, więc objazd przez tę koncepcję „trudności” jest całkowicie niepotrzebny.

— Glen Wheeler

7

Powód, dla którego ludzie sceptycznie podchodzą do prób dowodu P! = NP, jest tym samym powodem, dla którego ludzie są sceptyczni wobec dowodów jakiejkolwiek słynnej hipotezy: fałszywe dowody są publikowane co kilka miesięcy i zastrzelone. Tymczasem poprawne dowody słynnych przypuszczeń wydają się nie mieć trudności z przyciągnięciem uwagi, pomimo tego (patrz na przykład hipoteza Poincare'a lub ostatnie twierdzenie Fermata), ale dowody te często opierają się na głębokiej wiedzy o wysiłkach podejmowanych na dużą skalę przez grupy matematyków (takich jak przepływ Hamiltona Ricci dla hipotezy o poincare lub hipoteza Taniyama – Shimura – Weil dla ostatniego twierdzenia Fermata), nawet jeśli ostatnie kroki zostały wykonane przez jednego teoretyka.

P vs NP jest szczególnie trudnym problemem, ponieważ wszystkie „oczywiste” metody nie tylko nie dały dowodu, ale okazały się bezużyteczne przy mocnych twierdzeniach. Niedoszli dowódcy po raz pierwszy prawdopodobnie myślą, że natknęli się na dowód, ale wpadli w jedną z tych dobrze znanych pułapek. Co zaskakujące, głównym postępem w tej dziedzinie jest wykazanie, że wiele sposobów udowodnienia, że P! = NP nie może działać. To trochę oburzające, że nie możemy nawet wykazać, że 3Sat nie jest decydującym czasem liniowym, a tym bardziej poza czasem wielomianowym!

Twierdziłbym jednak, że bardzo niewiele osób uważa, że nigdy nie zostanie to udowodnione. Rzeczywiście, stwierdzenie P! = NP jest tak podstawową przeszkodą w naszym rozumieniu złożoności obliczeniowej, że trudno nie myśleć, że jest to prawdą z prostego i eleganckiego powodu.

Jeśli jednak ktoś chce być cyniczny, P! = NP jest równoważne stwierdzeniu, że fakt, że dowód jest łatwy (tj. Krótki), nie oznacza, że znalezienie dowodu nie jest bardzo trudne (tzn. Zajmuje czas wyszukiwania wielomianowego ). Rzeczywiście większość teorii uważa, że nie ma sub wykładniczego algorytmu czasowego znajdowania dowodów, który sugeruje, że biorąc pod uwagę jakąkolwiek metodę znalezienia dowodów (tj. Matematyka lub wyszukiwania komputerowego), istnieje wiele twierdzeń z prostymi krótkimi dowodami, które są niezwykle trudne znajdź (potencjalnie tysiąclecia czasu wyszukiwania). Czy P! = NP jest takim twierdzeniem, nie wiadomo oczywiście!

To powiedziawszy, ktoś może opublikować dowód jutro.

— olympicmarmot
źródło

4

Ponieważ możesz myśleć, że jest nierozstrzygalny, a może nawet nierozstrzygalny, czy jest nierozstrzygalny. Wiele twierdzeń matematycznych jest w ten sposób.

— Niklas Rosencrantz
źródło

11

Omawianie rozstrzygalności P vs NP jest błędem kategorii. Rozstrzygalność jest właściwością problemów obliczeniowych; P vs NP nie jest problemem obliczeniowym: jest to coś, co jest prawdziwe lub fałszywe (lub być może nie do udowodnienia). Najbliższa analogia brzmi: „Czy P = NP?” jest pojedynczym wystąpieniem jakiegoś innego problemu.

— David Richerby,

2

Ponadto {"Czy P = NP?"} Jest trywialnie rozstrzygalne, jak zostało to wcześniej omówione na stronie.

— Raphael

5

Jesteście trochę szybcy w oddawaniu głosu imho. Zgaduję, że odnosi się on do faktu, że hipoteza może być niezależna np. Od ZFC, która czasem jest również nazywana nierozstrzygalną ( en.wikipedia.org/wiki/Independence_(mathematical_logic) ).

— DFF

4

@David wyraźnie ustawia kontekst na „twierdzenia matematyczne”. W tym kontekście jedna z dwóch możliwych interpretacji tego terminu jest bezsensowna, wydaje mi się naturalne, że miał on na myśli drugą interpretację.

— DFF

3

@DFF, podejrzewam, że nie rozumiesz. Wielu informatyków rozumie pojęcie „niezależności”. Rozumieją także słowo „niezależność”. Problem pojawia się, gdy ktoś używa słowa „nierozstrzygalny” w znaczeniu „niezależny”, kiedy rozmawia z informatykiem - wśród informatyków domyślnie „niezdecydowany” będzie oznaczać „nierozstrzygalny” (jak problem zatrzymania) , a nie „niezależny”. Nie dlatego, że informatycy nigdy nie słyszeli o koncepcji niezależności, tylko dlatego, że mamy standardowe znaczenie terminu „nierozstrzygalny”.

— DW