Czy eksperci TCS powinni pobierać opłaty za czytanie dowodów, że P! = NP?

Dobrze wiadomo, że istnieje mnóstwo amatorów - w tym ja - którzy są zainteresowani problemem P vs. NP. Jest też wielu amatorów - w tym ja również - którzy próbowali rozwiązać problem.

Jednym z problemów, na który, jak sądzę, cierpi społeczność TCS, jest stosunkowo wysoki stosunek zainteresowanych amatorów do ekspertów; prowadzi to do zasypania ekspertów dowodami, że P! = NP, i czytałem, że są sfrustrowani i przytłoczeni, co zrozumiałe, tą sytuacją. Oded Goldreich napisał na ten temat i wskazał na własną odmowę sprawdzenia dowodów.

Jednocześnie, mówiąc z punktu widzenia amatora, mogę stwierdzić, że dla entuzjastów TCS o niskim poziomie umiejętności jest mniej frustrujących niż generowanie dowodów, które wydają się słuszne, ale brakuje im obu możliwość samodzielnego znalezienia błędu w dowodzie i możliwość rozmowy z każdym, kto może wykryć błędy w dowodzie. Ostatnio RJ Lipton napisał o problemie amatorów, którzy starają się być traktowani poważnie.

Mam propozycję rozwiązania tego problemu, a moje pytanie dotyczy tego, czy inni uważają to za rozsądne, czy też występują z tym problemy.

Myślę, że eksperci powinni pobierać znaczną, ale rozsądną sumę pieniędzy (powiedzmy 200–300 USD) w zamian za zgodę na szczegółowe czytanie dowodów i znajdowanie w nich konkretnych błędów. Osiągnęłoby to trzy rzeczy:

1. Amatorzy mieliby jasny sposób, by ich dowody zostały ocenione i potraktowane poważnie.
2. Eksperci otrzymaliby rekompensatę za poświęcony czas i energię.
3. Na weryfikację dowodów nałożono by znaczne koszty, że liczba dowodów przedłożonych przez amatorów dramatycznie spadłaby.

Ponownie moje pytanie dotyczy tego, czy jest to rozsądna propozycja. Oczywiście nie mam możliwości skłonienia ekspertów do przyjęcia tego, co sugeruję; Mam jednak nadzieję, że eksperci przeczytają to, co napisałem, i uznają to za uzasadnione.

Pozwól, że odpowiem na twoją sugestię kontrapugnią: dlaczego nie spróbujesz założyć firmy, działając jako pośrednik między amatorami i ekspertami? Amatorzy płacą za ocenę swoich dowodów. Znajdujesz eksperta i płacisz ekspertowi, aby ocenił dowód, przyjmując cięcia pieniędzy za rolę pośrednika. Próba prowadzenia takiej firmy to najbardziej niezawodny sposób na sprawdzenie, czy Twój pomysł jest wykonalny.

Mam trochę „rzeczywistego doświadczenia” w tej rodzącej się branży (i nie, nie mówię o mojej ofercie 200 000 $ dla Deolalikar :-))

W styczniu programista wysłał mi e-maila, że ​​miał próbę udowodnienia P ≠ NP, i chociaż był prawie pewien, że wystąpił błąd, nie mógł go znaleźć. Zapytał, czy znam jakichś studentów, którzy byliby gotowi znaleźć dla niego błąd w zamian za kilkaset dolarów.

Aby dać ci kontekst: dostaję dowód na P ≠ NP lub P = NP w mojej skrzynce odbiorczej mniej więcej raz w miesiącu. Wiele z tych e-maili trafia na długą listę teoretyków złożoności (Cook, Karp, Fortnow, Sipser ...); często zawierają religijne lub metafizyczne rozważania, a także ciemne wskazówki na temat spisków akademickich. (W jednym przypadku wystąpiły przeciwko mnie groźby śmierci, które doprowadziły mnie do skontaktowania się z policją.) Praktycznie żaden z nich nie uznaje żadnej możliwości, że dowód może być błędny lub że autor nie zrozumiał pytania. Kiedy w szkole dyplomowej próbowałem korespondować z autorami, okazało się, że wszyscy są gorącymi wyznawcami maksymy Churchilla: „nigdy, nigdy, nigdy, nigdy się nie poddawaj”.

Więc prośba twórcy oprogramowania naprawdę zrobiła na mnie wrażenie! To był pierwszy raz, kiedy widziałem dowód P ≠ NP, któremu towarzyszy ten poziom samoświadomości - zarówno na temat nakładania się na czas ludzi, jak i (co ważniejsze) na prawdopodobieństwo błędu. Tak się złożyło, że mój doktorant Michael Forbes przesłał autorowi piękny, szczegółowy raport wyjaśniający problemy z jego podejściem; autor podziękował Michaelowi i (myślę! :-)) zapłacił zgodnie z obietnicą.

Tak więc: dla amatorów, którzy chcą, aby ktoś sprawdził swoje dowody P lub NP (lub podobną pracę), uważam, że zapłacenie studentowi kilkuset dolarów jest świetną drogą. (Zauważ, że studenci są znacznie lepszym wyborem niż profesorowie: nie tylko mają więcej energii i entuzjazm do takich rzeczy, ale także potrzebują więcej pieniędzy.) Chciałbym, aby więcej amatorów skorzystało z tej opcji.

Przez kilka miesięcy pod koniec ostatniego roku studiów i na początku pierwszego roku studiów zarobiłem 60 USD na godzinę, korygując błędne dowody Amatora na ostatnie twierdzenie Fermata. W tym przypadku osoba ta była naukowcem z innej dziedziny, więc dobrze rozumiała wartość czasu eksperta. To było dobre doświadczenie, zarobiłem tysiąc dolarów w tym samym czasie, gdy nie miałem żadnych innych dobrych źródeł dochodu, a on nauczył się błędów, które popełnił w kilku projektach.

Myślę, że dla ludzi, którzy naprawdę się starają i są gotowi zapłacić dobre pieniądze, nie powinno być trudno znaleźć wykwalifikowanych studentów i młodych absolwentów, którzy potrzebują trochę pieniędzy.

Jednym z problemów, które widzę w twojej sugestii, jest to, że większość nie-dowodów P na NP nie jest nawet fałszywa. Innymi słowy, zwykle cierpią na brak definicji lub specyfikacji, który uniemożliwia ich weryfikację jako prawdziwą lub wykazanie, że jest fałszywa. Odsyłam cię do mojej (bezwstydnej alertu autopromocji!) Typowej interakcji między ekspertami a entuzjastą amatora P vs NP : trudno jest zobaczyć, jak wprowadzenie pieniędzy w tę dyskusję poprawiłoby to.

ps powyższa karykatura opiera się na oglądaniu wraków pociągów na teorii kompozycyjnej: Timothy Chow może mieć więcej do powiedzenia na ten temat, ponieważ często cierpliwie próbuje zaangażować takich ludzi.

Pamiętam, jak byłem na konferencji językowej około 1985 roku, gdzie odbyła się następująca wymiana:

Mówca: Liście drzewa są przypadkami problemu NP-zupełnego, ale są łatwe do rozwiązania ręcznie.

Ja: Jeśli instancje są łatwe do rozwiązania, być może problem nie jest NP-zupełny.

Mówca: nie rozumiem.

300 USD wydaje się za mało, by je naładować. Opłaca się za godzinę lub 2. Jakikolwiek dowód, że brak jest już wykluczony.

Absolutnie nie. Nie potrzebujemy kolejnej akademickiej alternatywy. Niektóre osoby już zapewniły takie alternatywy, zapewniając zarówno amatorom, jak i zawodowym badaczom i społeczeństwu fałszywe nadzieje na przyszłość zaawansowanych technologii (mam na myśli szczególne miejsce, ale wolałbym o tym nie wspominać).

System akademicki został ukształtowany po wiekach w to, czym jest. Widzę próby pominięcia systemu recenzowania jako po prostu „pomijanie linii”. Jeśli amatorska badaczka nie jest w stanie zrozumieć, dlaczego jej dowód jest błędny, samodzielnie lub z komentarzami z recenzji, istnieje proste rozwiązanie i to znaczy, że musi ona dokładniej przestudiować ten temat. Właśnie dlatego istnieją instytucje edukacyjne, takie jak uniwersytety, które poświadczają znajomość określonej osoby. Jeśli ta osoba okaże się geniuszem, który natychmiast zrozumie wiedzę w tej dziedzinie, przyznaj ten stopień tak szybko, jak to możliwe. Jednak zdecydowana większość musi i powinna przejść szkolenie dla siebie i społeczeństwa.

Co byś pomyślał, gdyby ta branża została zaczerpnięta z matematyki i skierowana na medycynę lub inną dziedzinę, w której konsekwencje są bardziej bezpośrednie? Jak długo celowo niewiarygodny biznesmen zmienia papiery amatorskie, tak że trudno jest je przejrzeć lub oszukać recenzenta? Oszukiwanie klientów-badaczy-amatorów na pewno się wydarzy, tak jak w przypadku wszystkich firm, które polegają na trudnym zdobyciu wiedzy.

Widać, że mam na myśli to, że istnieją problemy funkcjonalne, zanim sięgną do szczegółów technicznych. A skoro wygłaszam argumentację inżynierską, „programowanie” jest dobrym przykładem tego, co dzieje się, gdy amatorzy starają się wykonywać poważną pracę przy niewielkim lub żadnym szkoleniu. Ostatnią rzeczą, jakiej potrzebuje każda społeczność naukowa, są gloryfikacja kolejnego „samouka informatyka teoretycznego, który rzuca wyzwanie fundamentom całej społeczności naukowej ze swojego garażu”, nie mówiąc już o kruchej nauce jako naszej, która wciąż stara się ją docenić. zasługuje.