Materiały do ​​nauki o problemie P vs. NP

Niedawno przypomniano mi o problemie vs. jak wyjaśnił Stephen A. Cook z Clay Mathematics Institute.N $\mathsf{P}$$\mathsf{NP}$

To wzbudziło moje zainteresowanie i chciałbym dowiedzieć się więcej na ten temat. Pierwszym krokiem byłoby lepsze zrozumienie problemu i ogólne zrozumienie tego obszaru.

Czy możesz polecić jakieś książki lub inne zasoby, w których mogę dowiedzieć się więcej na temat problemu?

Dobrze jest widzieć kolegę z tego entuzjazmu w realizacji tego wielkiego problemu. Pozwól, że dam ci radę z moich własnych doświadczeń.

jest bardzo interesującym problemem. Implikacje odpowiedzi są ogromne, szczególnie w przypadku, gdy obie klasy są równe. Nagroda jest wielka na wielu poziomach, od altruistycznego naukowego do materialistycznej nagrody pieniężnej. To prowadzi wielu młodych ludzi, którzy napotykają problem, próbując go rozwiązać, bez wiedzy na ten temat lub z ograniczoną wiedzą.$P \neq NP$

Być może większość studentów teorii przechodzi tę fazę. Będziesz miał pomysł i pomyślisz, że jest słuszny, ale jest prawie pewne, że się mylisz. Niektórzy ludzie nigdy nie przechodzą przez tę fazę i zawstydzają się, będąc zbyt upartymi, by przyznać się do swoich błędów.

W FOCS 2010 Rahul Santhanam porównał pytanie do mitycznego potwora. Potrzeba było wielu poświęceń i odwagi, aby nawet spróbować pokonać tego potwora. W końcu może to być najtrudniejszy problem w historii. Aby mieć szansę na walkę, będziesz musiał dużo przestudiować ten problem i złożoność w ogóle. Nigdy nie dowiesz się, jaka będzie „słabość potwora”.$P \neq NP$

Moja rada jest następująca: nie spiesz się w poznaniu problemu. Za każdym razem, gdy znajdziesz rozwiązanie, załóż, że się mylisz i spróbuj znaleźć problem. W ten sposób wiele się nauczysz.

Jeśli chodzi o referencje, poleciłbym również książkę Sipsera. Po jego zakończeniu poleciłbym Arora i Barak, „Złożoność obliczeniową: nowoczesne podejście”, książkę bardziej zorientowaną na złożoność, która wymaga dobrego zrozumienia pojęcia obliczeń.

Zdecydowanie sugeruję „Wprowadzenie do teorii obliczeń” Sipsera, szczególnie dlatego, że obejmuje on co najmniej jedną z głównych barier w rozwiązywaniu P vs. NP, a mianowicie relatywizację. Zawiera bardzo wyraźny dowód wyniku Baker-Gill-Solovay. Nie jestem pewien, czy zawiera on coś w wynikach Razborova-Rudicha, ale jest to fantastyczny, bardzo jasny i łatwy do odczytania materiał wprowadzający do nauki nie tylko o P vs. NP, ale także o wielu innych powiązanych tematach w teorii złożoności. ... co jest znaczące, ponieważ jeśli Twoim zainteresowaniem jest próba rozwiązania problemu, będziesz potrzebować trochę doświadczenia w terenie i pomysłów, od czego zacząć.

Prawdopodobnie najlepszy zbiór linków w jednym miejscu, to kolejna sekcja Odczyt z wiki, które zostały połączone, aby pomóc w ocenie Deolalikar twierdził dowód, że .$P \neq NP$

Powodzenia. Problem wydaje się być trudny. :-)

Oto jeden z najlepszych artykułów ankietowych na temat problemu P vs NP, , N P i matematyki - perspektywa złożoności obliczeniowej$P$$NP$ autorstwa Wigderson

Klasycznym źródłem kompletności NP jest książka Gareya i Johnsona (http://tinyurl.com/2w5yofs). Jest pouczający i dokładny.

Osobiście uczyłem się od Kleinberga Tardosa (http://tinyurl.com/37dtyyl), ponieważ mój uniwersytet go używał.

Sugerowałbym również wzięcie problemu i spróbowanie go rozwiązać. Dobrą praktyką jest eksperymentowanie z otwartymi problemami. Przez eksperyment mam na myśli, że możesz pisać programy lub implementować znane algorytmy przez innych i rozumieć, jak one działają, gdzie zawodzą itp. Możesz także odkryć kilka technik dowodowych. Pamiętaj, że nie wsadzą cię do więzienia, jeśli będziesz dużo się uczył i pracował i nie mógł znaleźć żadnego rozwiązania. Przeciwnie, Twój poziom kompetencji z pewnością wzrośnie.

W większości przypadków problemy te są ogólnie trudne do rozwiązania niż ich konkretne przypadki . Przeczytaj o NFL, aby uzyskać pomysł.

W moim przypadku zostałem wkrótce pochowany pod pulą pomysłów i powiązanych koncepcji. Są poprawki w programowaniu / kodowaniu i są teoretyczne manewry. Na przykład, jeśli chcesz rozwiązać problem za pomocą algorytmu genetycznego, wkrótce odkryjesz, że sama GA to ogromny świat do odkrycia! Niedawno dowiedziałem się o Linkage Learning w GA / EA. Jednak niewiele o tym wiem.

Ponadto, gdy spróbujesz kodować różne rzeczy, zauważysz, że niektóre języki programowania / narzędzia są lepsze / łatwiejsze niż inne. Zagubiłem się w dyskusji, dlaczego Alex Stepenov uważa, że ​​OOP jest matematycznie niepoprawny i jaka jest zaleta programowania funkcjonalnego. Nie mam śladu, ale wyraźnie pamiętam, że na początku studiowałem problem NP-Complete / Hard.

Witam was, ponieważ podróż jest pełna przygód!

P, NP i NP-Kompletność: podstawy teorii złożoności autorstwa Odeda Goldreicha byłyby kolejną dobrą książką wprowadzającą.

Po wprowadzeniu chciałbym również polecić Pytanie P = NP i Zagubiony list Richarda J. Liptona Gödela .

Polecam doskonały artykuł poglądowy autorstwa Lance'a Fortnowa „Status problemu P w porównaniu z NP” , który omawia kilka nowych podejść do problemu.

$P=?NP$$\mathcal{P}$$\mathcal{NP}$

Lance Fortnow niedawno rozszerzył i opublikował swoją obszerną już kolumnę z CACM (wspomnianą w innej odpowiedzi magistra) do pełnej długości książki popularnonaukowej, The Golden Ticket: P, NP i Search for the Impossible . został opublikowany przez Nazaryan w „ New Yorker”, „ Najgłębszy problem matematyczny” . ( strona wydawców , Princeton University Press)