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