211service.com
Co oznacza „P kontra NP” dla reszty z nas?
Programiści i informatycy od tygodnia szumią o ostatniej próbie rozwiązania jednego z najbardziej dokuczliwych pytań w informatyce: tak zwanego problemu P kontra NP.
Vinay Deolalikar, naukowiec z HP Labs w Palo Alto w Kalifornii, umieścił swój dowód w Internecie i wysłał go do kilku ekspertów w tej dziedzinie 6 sierpnia. Koledzy natychmiast zaczęli analizować dowód na akademickich blogach i wiki. Wczesne reakcje były pełne szacunku, ale sceptyczne, a obecny konsensus jest taki, że podejście Deolalikar jest fundamentalnie wadliwe.
Solidny dowód przyniósłby Deolalikarowi sławę i fortunę. ten Instytut Matematyki Gliny w Cambridge w stanie Massachusetts wymienił P kontra NP jako jeden ze swoich problemów milenijnych i oferuje milion dolarów każdemu, kto przedstawi zweryfikowany dowód.
Ale P versus NP to coś więcej niż abstrakcyjna matematyczna zagadka. Stara się ustalić raz na zawsze, jakie rodzaje problemów mogą być rozwiązane przez komputery, a jakie nie. Problemy klasy P są łatwe do rozwiązania przez komputery; to znaczy, rozwiązania tych problemów można obliczyć w rozsądnym czasie w porównaniu ze złożonością problemu. Tymczasem w przypadku problemów z NP rozwiązanie może być bardzo trudne do znalezienia – być może wymagałoby to obliczeń trwających miliardy lat – ale raz znalezione, łatwo je sprawdzić. (Wyobraź sobie układankę: znalezienie odpowiedniego ułożenia elementów jest trudne, ale możesz stwierdzić, kiedy układanka jest poprawnie ukończona, po prostu na nią patrząc.)
Problemy klasy NP obejmują wiele problemów związanych z dopasowywaniem wzorców i optymalizacją, które są bardzo interesujące z praktycznego punktu widzenia, takich jak określanie optymalnego rozmieszczenia tranzystorów na chipie krzemowym, opracowywanie dokładnych modeli prognoz finansowych lub analizowanie zachowań związanych z fałdowaniem białek w komórce.
Problem P versus NP pyta, czy te dwie klasy są rzeczywiście identyczne; to znaczy, czy każdy problem NP jest również problemem P. Jeśli P równa się NP, każdy problem NP zawierałby ukryty skrót, pozwalający komputerom na szybkie znalezienie dla nich idealnego rozwiązania. Ale jeśli P nie równa się NP, to nie ma takich skrótów, a możliwości rozwiązywania problemów przez komputery pozostaną zasadniczo i trwale ograniczone. Praktyczne doświadczenie w przeważającej mierze sugeruje, że P nie równa się NP. Ale dopóki ktoś nie przedstawi solidnego matematycznego dowodu, słuszność tego założenia pozostaje otwarta.
Nawet jeśli dowód Deolalikara okazałby się solidny, pozostaje pytanie – jaki wpływ miałby taki dowód na odpowiednie obszary informatyki?
Pozornie można by pomyśleć, że odpowiedź brzmi niewiele. Udowodnienie, że P nie jest równe NP, potwierdziłoby tylko to, co prawie wszyscy już zakładają jako prawdziwe dla celów praktycznych, wyjaśnia Scott Aaronson , badacz złożoności w Laboratorium Informatyki i Sztucznej Inteligencji MIT.
Na przykład nasza niezdolność do efektywnego rozkładania na czynniki ogromnych liczb złożonych (klasyczny problem NP) stanowi podstawę nowoczesnej kryptografii – która stanowi podstawę wszystkiego, od bezpieczeństwa narodowego po zakupy na Amazon.com. Nie potrzebujemy formalnego dowodu, że P nie jest równe NP, aby oprzeć się na przypuszczeniu, mówi Aaronson. Programiści wiedzą o problemie i byliby podekscytowani, gdyby okazało się, że P nie równa się NP, ale na co dzień wiedzą, że przeformułowanie [problemu NP] na coś łatwiejszego ma o wiele większy sens niż próba rozwiązania matematycznego problem stulecia.
Ponieważ problemy klasy NP są tak wszechobecne (nawet łamigłówki sudoku i wyszukiwanie rozkładów lotów na Bing.com są trudne obliczeniowo), ciągle odkrywane są innowacyjne rozwiązania. Optymalizacja stochastyczna na przykład naśladuje losowość występującą w układach fizycznych (takich jak chłodzące metale lub mutujące DNA) w celu uzyskania wystarczająco dobrych rozwiązań zamiast trudnych obliczeniowo.
Próby poradzenia sobie z założeniem, że P nie równa się NP, pomagają nam rozwijać nowe technologie umysłowe, mówi Ryszard Lipton , informatyk z Georgia Tech, który bada problem P kontra NP. Mimo że piszemy algorytmy od dziesięcioleci, nie do końca rozumiemy, do czego są zdolne – kontynuuje. Więc nawet jeśli udowodnisz, że P nie równa się NP – w co wszyscy już wierzą – musiałoby to radykalnie poszerzyć nasze zrozumienie tych możliwości i umożliwić wiele nowych rzeczy dzięki komputerom, oprócz wszystkich sprytnych rozwiązań, które już mamy. znaleziony.
Jeśli więc stopniowy postęp może nadal generować użyteczne innowacje, dlaczego tytani badań przemysłowych, tacy jak Google, Microsoft i HP (z których wszyscy odmówili komentarza do tego artykułu) nie poświęcają ogromnych zespołów badaczy na P nie równa się zagadce NP? Udowodnienie negatywnego wyniku jest po prostu niewiarygodnie trudne, a z punktu widzenia [dużej firmy] prawdopodobnie nie ma większego wpływu na następny kwartał finansowy ani nawet na kilka następnych lat ich działalności, mówi Lipton. To bardziej problem długoterminowy.
Oczywiście zawsze jest alternatywa: udowodnienie, że P czy w rzeczywistości równy NP. Ale nie wstrzymuj oddechu, mówi Aaronson. Są dobre powody, dla których niewiele osób wierzy, że P równa się NP, mówi. Gdyby tak było, żylibyśmy w całkowicie innym wszechświecie i prawdopodobnie już byśmy to zauważyli.