Dowodzenie P = NP bez instrukcji matematycznych / programu komputerowego

To mój pierwszy post po tym, jak od jakiegoś czasu jestem pasywnym użytkownikiem. Chciałbym zadać kilka pytań, jeśli mogę. Nie jestem matematykiem, ale moje pytanie dotyczy matematyki / informatyki. W szczególności problem P vs NP. Wiem, że jest to problem, którego elitarni specjaliści nie byli jeszcze w stanie rozwiązać ...

Niezależnie od tego chciałbym zapytać:

Jeśli osoba, która nie jest ani matematykiem, ani programistą, opracuje schemat blokowy lub serię kroków napisanych w podstawowym języku angielskim, które rzekomo stanowią rozwiązanie jednego z problemów P vs NP, można by to uznać za „udowodnienie”, że P = NP .. aby ubiegać się o nagrodę Clays Institute :)? Czy może trzeba napisać rozwiązanie jako dowód matematyczny / program komputerowy?

Dziękuję Ci.

„Nie”, możesz użyć „podstawowego angielskiego”.

Jeśli ci się uda, stworzyłbyś konstruktywny dowód . Dowody w matematyce są często mieszanką „podstawowego angielskiego”, jak go nazywacie, i wzorów matematycznych, ale nie muszą zawierać żadnego z nich, aby być ważnym dowodem.

Załóżmy, że masz taki schemat blokowy, co musisz udowodnić - tzn. Argumentować - że Twój algorytm działa dla każdego wystąpienia problemu. Sposób, w jaki to robisz, zależy wyłącznie od ciebie, o ile dowód jest jednoznaczny, a wszystkie przesłanki, które twierdzisz, są prawdziwe.

Po zrobieniu tego masz w rękach matematyczny dowód . Tak naprawdę powinienem był powiedzieć „ tak ” na początku, potrzebujesz matematycznego dowodu .

Należy pamiętać, że maszyna Turinga jest rodzajem schematu blokowego. Podobnie jak struktura programu komputerowego. Tak więc przekształcenie „schematu blokowego” w formalną odpowiedź na problem powinno być dość łatwe, jeśli faktycznie zadziałało. Rzeczywiście, jeśli zaczniemy od strasznie formalnej odpowiedzi na P w porównaniu z NP , większość informatyków spróbuje znaleźć jej sformułowanie, które jest jak najbardziej zbliżone do prostego angielskiego opisu, aby uzyskać tak dobre zrozumienie rozwiązania, jak możliwy.

Ale istnieje podstawowy problem z pytaniem, które zadajesz. Co to znaczy, że ktoś, kto byłby w stanie rozwiązać P w porównaniu z NP - i pokazując, że są równi, nie mniej - nie jest ani informatykiem, ani matematykiem? Być może nie są zatrudnieni zawodowo jako informatyk lub matematyk, ale nie ma to znaczenia, jeśli mają umiejętność rozwiązania tego, co niektórzy (na przykład Scott Aaronson) opisują jako najważniejszy problem matematyczny, jaki kiedykolwiek rozważaliśmy. Jeśli ktoś przeszedł szkolenie (lub nawet samouk), aby skutecznie rozwiązać problem, a także w jasny sposób przekazać rozwiązanie innympoprzez identyfikację głównych podprogramów i ich roli w rozwiązywaniu np. SAT lub HAMPATH, to, czy są zatrudnieni, czy nawet mają stopnie naukowe, jest nieistotnym szczegółem; są jednak matematykiem lub informatykiem. Jeszcze lepiej, jeśli potrafią opisać, w jaki sposób ich rozwiązania pokonują klasyczne przeszkody, takie jak wyniki wyroczni, takie jak wyrocznie A, dla których P ^A ≠ NP ^A (lub odwrotnie), pokazując konkretnie, jaką strukturę ma problem z algorytmem, który nie byłyby dostępne w modelu Oracle. Problemem jest jednak to, że większość ludzi, którzy marzą o rozwiązaniu P kontra NP jako amatorzy lub osoby z zewnątrzwydaje się, że brakuje im umiejętności komunikacyjnych, aby właściwie opisać swoją pracę, lub (z powodu braku wystarczającej wiedzy) nie są świadomi wyników, które od samego początku byłyby skazane na rozwiązanie problemu.

Podobnie jak w przypadku wszystkich marzeń o chwale w dzisiejszych czasach, istnieje podstawowy problem z fantazją bycia tą, która rozwiąże P kontra NP . Problem polega na tym, że będzie to prawie niemożliwe. W rzeczywistości nie jest to niemożliwe, pamiętaj o Tobie, a przynajmniej niekoniecznie niemożliwe; prawie tak. Jako ktoś bystry i ambitny, można stracić z oczu fakt, że jest wielu innych bystrych ludzi: wielu z nich również myślało o problemie; i wielu z nich jest jaśniejszych od siebie, nawet o kilka rzędów wielkości. I że istnieli tak błyskotliwi ludzie, dopóki istniał problem; a jednak pozostaje nierozwiązane. Tak, w zasadzie możliwe jest, że wszyscy myślą o tym w niewłaściwy sposób, i to od dziesięcioleci. Ale czy to jest tonaprawdę szczególnie prawdopodobne? Nikt nie powinien oczekiwać, że będzie jedyną osobą, która może dostrzec błąd jednego znaku, który wszyscy popełniają, ponieważ jeśli wszyscy inni popełniają ten błąd, musi być coś w problemie, który doprowadzi do tego samego błędu. Lub - w bardziej prawdopodobnym przypadku, gdy przyczyną, dla której problem pozostaje nierozwiązany, nie jestże ludzie popełniają proste błędy lub jeszcze nie wymyślili jednej prostej sztuczki, która rozwiązuje całą sprawę - to, co sprawia, że ​​problem jest zasadniczo trudny, jest zasadniczo obiektywną trudnością problemu, a żadne sprytne kroki taneczne nie pozwolą po prostu walcować z wdziękiem ominąć wszystkie przeszkody; wymagane jest podejście, które nie jest jedynie nowatorskie, ale dość głębokie, identyfikując subtelne struktury, których nikt wcześniej nie widział. Rodzaj struktury, którą można dostrzec, stale myśląc o problemie przez lata.

Jeśli chcesz być realistą w kwestii rozwiązania problemu P kontra NP , możesz porównać go do podobnych słynnych przełomów w ciągu ostatnich kilku dekad, takich jak dowody czterokolorowego twierdzenia, ostatniego twierdzenia Fermata lub Hipoteza Poincarégo. Mogą kiedyś mieć prostsze dowody, ale oryginalne dowody zabierają cię daleko w dzicz, aby doprowadzić cię do końca (lub w przypadku twierdzenia Czterech Kolorów trasa jest bardzo długa i powtarzalna). Nie ma szczególnego powodu, aby podejrzewać, że P w porównaniu z NP będzie inny; tak, jeśli w końcu tak jestrozwiązane przez amatora, są bardzo duże szanse, że byłby to ktoś o podobnej wiedzy i znajomości technik kogoś, kto ma wykształcenie akademickie. Każdy realistyczny amator, który marzy o rozwiązaniu P kontra NP , dobrze by to zrobił.

Dowód, że P = NP może zostać zaakceptowany przez czasopismo matematyczne, ale elity nigdy nie zostaną zaakceptowane. Powodem jest to, że wiedzą, że P! = NP (przynajmniej dla wszystkich praktycznych celów). Wiedzą również, że udowodnienie tego jest niewiarygodnie trudne, więc nawet dowód, że P! = NP zostanie przyjęty ze sporą dozą sceptycyzmu przez elitarnych specjalistów.

Elitarni specjaliści mają bardziej skomplikowane powody niż to, że wiele jasnych umysłów próbowało i nie udało się zbudować algorytmu wielomianowego dla NP lub udowodnić, że N! = NP. Racjonalnie oczekują jednak, że ten argument powinien być najbardziej przekonujący dla laika. Prawdopodobnie mają rację, że odniesienie do barier związanych z relatywizacją dowodów, dowodów naturalnych lub dowodów algebrizing rzadko jest przekonujące dla osoby niebędącej ekspertem. Jeśli zbyt wielu „amatorów” spróbuje rozwiązać P vs NP w określony sposób (na przykład przez rozwiązanie logiczne lub sprowadzając go do problemu programowania liniowego), wówczas ktoś przejdzie przez ból (to czasami zajmuje lata), aby udowodnić, że ten konkretny kąt ataku jest prawdopodobnie skazany na niepowodzenie.

Edytuj Cieszę się, że ta odpowiedź nadal przyciąga (negatywne) opinie. Pozwolę sobie zatem zastąpić drugą część odpowiedzi (która wydaje się niezwiązana z opiniami, ale może odwrócić uwagę od głównego punktu) następującym cytatem z Truth vs. Proof :

Moglibyśmy pozostać agnostykami, mówiąc, że po prostu nie wiemy, ale może istnieć coś takiego jak zbyt duży sceptycyzm w nauce. Na przykład Scott Aaronson kiedyś twierdził, że w innych naukach P! = NP zostałby już uznany za prawo natury. Zwykle się zgadzam. W końcu staramy się odkryć prawdę o naturze obliczeń, a ta misja nie pójdzie szybciej, jeśli nalegamy na odrzucenie wszystkich dowodów, które nie są w postaci matematycznych dowodów z pierwszych zasad.

Ta zmiana nie ma na celu zmniejszenia ilości informacji zwrotnych, ale wyjaśnienie, że odpowiedź jest poważna w związku z faktem, że eksperci „wiedzą, że P! = NP”, nawet jeśli nie mogą tego udowodnić.

23 listopada 2013 Jeszcze raz dziękuję za wszystkie opinie. Dla przypomnienia, odpowiedź ma teraz 7 głosów negatywnych, 1 głosowanie pozytywne i 14 komentarzy (8 przeze mnie). Ze względu na ilość komentarzy ciekawe referencje i uzasadnienia podane w komentarzach są ukryte, dlatego postanowiłem dodać niektóre z nich tutaj:

• Jak sam Gödel napisał do von Neumanna, gdyby P = NP były prawdziwe „dla wszystkich praktycznych celów”, to jego twierdzenie o niekompletności byłoby prawdziwe tylko w teorii, ale faktycznie fałszywe w praktyce.

• W swoim artykule z 1971 r. Stephen Cook ... nie był w stanie wyprodukować kontrpróbek dla procedury Davisa-Putnama (rozwiązany przez Haken 1985). Obecnie dostępnych jest wiele technik, wyników i kontrprzykładów dla „obalenia” proponowanych wydajnych solverów NP. Również P = NP jest sprzeczne z „prawem zachowania trudności”, „jakościową nieskończonością <-> ilościowo finalną”…

• Dawno temu Scott Aaronson napisał ten komentarz :

  anonimowy: Twierdzisz (jako fakt!), że 3SAT jest językiem w NP, którego nie można obliczyć w czasie wielomianowym. Ale nie możesz tego udowodnić. Czy to twoja metoda naukowa? Tak. Jako głęboko wierzący w naukę i rozum staram się wyraźnie rozróżniać między tym, co mogę udowodnić, a tym, co po prostu wiem, że jest prawdą.

• Scott jest znany z tego, że próbuje udowodnić, co to znaczy, że coś „wie”, na przykład obstawiając 200 000 $: scottaaronson.com/blog/?p=458