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

12

Niedawno przypomniano mi o problemie vs. jak wyjaśnił Stephen A. Cook z Clay Mathematics Institute.N PP.N.P.

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?

Jon Cox
źródło
Przesłane z math.stackexchange.com/questions/13742/... , na które obecnie nie ma odpowiedzi.
Tsuyoshi Ito,

Odpowiedzi:

11

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.N.P.

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.N.P.

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

chazisop
źródło
4
Dziękuję za słowa mądrości. Jeśli jestem całkowicie szczery, im więcej dowiaduję się o problemie, tym bardziej niemożliwe wydaje się znalezienie rozwiązania. Z pewnością bardzo interesujące!
Jon Cox,
4
+1 Podoba mi się, ale nie zgadzam się. nie jest potworem, ale bardzo piękną laską czekającą, aż ktoś podniesie jej zasłonę, aby świat mógł cieszyć się jej chwalebnym pięknem. Poza tym jest bardzo niewinna i czysta, a ona po prostu próbuje się z nami bawić i drażnić się z nami swoimi łamigłówkami ...P.vsN.P.
Mohammad Al-Turkistany,
2
Ponadto, jeśli byłaby potworem, natychmiast przestałabym ją ścigać, ponieważ nienawidzę potworów :)
Mohammad Al-Turkistany,
9

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ąć.

Philip White
źródło
Dziękuję za sugestię, zdobędę kopię z biblioteki i przejrzę ją :)
Jon Cox
7

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.N.P.

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

Aaron Sterling
źródło
7
wydaje się być twardym, to bardzo niedoszacowany opis twardości P w porównaniu z NP. :)
Hsien-Chih Chang 之 之
Dziękujemy za sugestię, istnieje wiele materiałów do sprawdzenia.
Jon Cox,
4

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

Gautam Kamath
źródło
Znakomicie, mam już kopię książki Klienberg Tardos na kurs, który robię, i dziś jeszcze zdobędę książkę Gareya i Johnsona z biblioteki. Dziękujemy za poinformowanie mnie o tym.
Jon Cox,
3

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!


źródło
2

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.

Marko Amnell
źródło
Dziękujemy za poinformowanie mnie o tym artykule, zdecydowanie wygląda na to, że warto go przeczytać.
Jon Cox,