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.

complexity-theory p-vs-np

— Raphael
źródło

Zobacz tę kolekcję: win.tue.nl/~gwoegi/P-versus-NP.htm . Nie chcesz zostać jednym z nich.

— Yuval Filmus

istnieje jeden możliwy „słaby” precedens. Godels thm i diagonalizacja mogły być luźno oparte na paradoksie Richardsa, który był dziełem literackim. ale zauważ, że bardzo zaawansowani matematycy zajęli się przekształceniem go w prawdziwe stwierdzenia / właściwości matematyczne.

— vzn

@vzn: strona Wikipedii, do której prowadzą linki, datuje Paradoks Richarda do 1905 r .; diagonalizacja sięga 1891 roku. Paradoks Richarda prawdopodobnie opiera się na diagonalizacji, a nie na odwrót.

— Niel de Beaudrap

@NieldeBeaudrap, vzn: Twoje komentarze zamieniły się w rozmowę, więc przeniosłem je na czat , kontynuuj tam.

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

Odpowiedzi:

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

— phant0m
źródło

Nie dajmy tu nikomu fałszywych nadziei. Jest bardzo mało prawdopodobne, aby laik mógł rozwiązać

vs.

, lub że rozwiązanie może być wyrażone w „zwykłym języku angielskim”. Dla świeckich są lepsze rzeczy do zrobienia niż rozwiązywanie najtrudniejszych problemów matematycznych.

P

$P$

N P

$NP$

— Andrej Bauer

@AndrejBauer Jasne, nie chciałem sugerować, że to prawdopodobne. Zakładam, że wolałbyś odpowiedź podobną do Niel . Ale chociaż dobrze przedstawia perspektywę, tak naprawdę nie odpowiada na zadane pytanie.

— phant0m

Wiem, że nie chciałeś sugerować czegoś takiego. Chciałem tylko wyrazić wyraźne ostrzeżenie, aby dziennikarz lub ktoś to nie przeczytał i nie pomyślał, że

kontra

rozwiąże krytyk literacki.

P

$P$

N P

$NP$

— Andrej Bauer

@ phant0m: Jestem ciekawy. Czy mój pierwszy akapit nie odnosi się do rzeczywistego pytania?

— Niel de Beaudrap

@NieldeBeaudrap Jasne, że to rozwiązuje, ale wydaje się, że należy wyciągnąć wniosek. Sidenote: Można również zinterpretować "Indeed"zdanie jako podające wyjaśnienie dowodu w słowach, ale samo w sobie nie byłoby dowodem. Również maszyna Turinga sama w sobie nie jest dowodem, chyba że podany zostanie dowód poprawności. Oznacza to również, że prezentowanie TM na schemacie blokowym jest z natury lepsze jako „dowód”, nawet jeśli nie jest.

— phant0m

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

— Niel de Beaudrap
źródło

Chociaż wszystko, co mówisz, jest prawdą, obawiam się, że ten sposób myślenia (który stał się powszechny w terenie, być może jako mechanizm ochronny) może zniechęcić jedynego geniusza, który nauczyłby się dziś rozwiązać problem. Myślę, że bardziej pomocnym przesłaniem jest: idź i zdobądź tyle szkoleń, ile potrzebujesz, aby przekonać choćby jednego specjalistę, najpierw przeczytaj swoją pracę, a następnie jej ważność. Może to potrwać lata, ale to jest właściwa droga.

— Raphael

@Raphael: Myślę, że w rzeczywistości moja mentalność jest doskonale dostosowana nawet do możliwości geniuszu samouka. Moje przesłanie do geniuszu samouka jest takie: z jednej strony nie bycie akademikiem nie oznacza, że nie jesteś matematykiem - i że oceniłbym odpowiedź na podstawie jego jakości. Na tym spoczywa więc geniusz samouka, aby upewnić się, że odpowiedź ma jakość, i uważać na pułapki, na które amatorzy często padają ofiarą.

— Niel de Beaudrap

Obawiam się, że ten sposób myślenia ... może zniechęcić jedynego geniusza samouka, który mógłby dziś rozwiązać problem. - Dobry. Twojemu samoukowi geniuszowi należy przypomnieć, że poprzeczka jest wyjątkowo wysoka i że dziesiątki (setki?) Innych geniuszy samouków próbowało jej nie osiągnąć.

— JeffE

„Ostatnie twierdzenie Fermata lub hipoteza Poincarégo. Mogą kiedyś mieć prostsze dowody, ale oryginalne dowody zabierają cię daleko w dzicz, aby dotrzeć do końca (lub w przypadku twierdzenia Czterech Kolorów trasa jest bardzo długa i powtarzalne) ”. jest to oczekiwanie przez niektórych słuszne / rozsądne, ale z drugiej strony, w przeciwieństwie do arbitralnych teoretycznych ciekawostek, takich jak FLT i 4CT, można stwierdzić, że dowód P vs NP może dostarczyć (fundamentalne) narzędzia dla innych separacji klas złożoności i ogólnej teorii złożoności lub może być nawet kamień z Rosetty lub brakujące ogniwo do późniejszego awansu ..

— vzn

@vzn: Nie jestem do końca pewien, do czego zmierza to rozróżnienie. Tylko dlatego, że P kontra NP jest ważne, nie sprawia już, że istnieje prawdopodobieństwo znalezienia prostego rozwiązania, które mógłby znaleźć sprytny, ale niewtajemniczony amator.

— Niel de Beaudrap

-5

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

— Thomas Klimpel
źródło

\neq

$\neq$

Nikt nie „wie”, że P! = NP. Eksperci mogą w to mocno wierzyć, ale żaden ekspert nie wie o tym (chyba że ktoś ma dowód i zachował go dla siebie). Możliwe, choć mało prawdopodobne, że P = NP jest prawdziwe. Na marginesie, wszyscy (zwłaszcza naukowcy) powinni być otwarci na wszystko, chyba że udowodniono inaczej. W tym przypadku każdy naukowiec, bez względu na to, jak duże jest jego przekonanie, że P! = NP, powinien zaakceptować, że istnieje możliwość, że P = NP.

— George

W matematyce problemem ignorowania dowodu i ślepego postępowania jest to, że możesz założyć, że coś jest nie tak. Spowoduje to, że zadanie będzie przebiegać znacznie wolniej. Nauki fizyczne nie mają tego problemu (z wyjątkiem przypadków takich jak grawitacja kwantowa / teoria strun), ponieważ muszą zgodzić się z eksperymentem.

— Peter Shor,

@ThomasKlimpel: Pamiętam, że opublikowałem ten komentarz, ale nie gdzie. Biorąc pod uwagę, że ktokolwiek odpowiadałem (tobie?) Po prostu używał go jako autorytetu do argumentowania za poprawnością matematycznego platonizmu, podczas gdy ja po pewnym rozważaniu doszedłem do stanowiska formalistycznego, sam fakt, że Godel miał inną opinię bez dalszego wyjaśniania opracowanie jest rzeczywiście nieistotne. Argumenty techniczne nie są wygrywane jak mecze tenisa, z szybkim obaleniem. Podobnie przekonujące odpowiedzi są oceniane nie tylko na podstawie ich skrupułów (choć to pomaga), ani na podstawie autorytetu, ale na podstawie ich zalet technicznych.

— Niel de Beaudrap,

\neq

$\neq$