Dziewczyna, która udowodniła, że P = NP

Oryginalny post: The Girl Who Proved P = NP

Autor: Jeff Atwood

Jeden z moich ulubionych blogowych wpisów przedstawia prawdziwie epicką historię nieudanej randki, którą wieńczy chyba najdziwniejsze odniesienie do problemu P=NP, jakie kiedykolwiek napotkasz.

Joey: Naprawdę skończyłaś informatykę?

Nowa Dziewczyna: Tak, na UBC!

Joey: I uczęszczałaś na kurs "Algorytmy"?

Nowa Dziewczyna: Jasne!

Joey: Zachowałaś wszystkie swoje artykuły?

Nowa Dziewczyna: Tak! Wszystkie! Pokażę Ci je jutro!

Joey: Chętnie zobaczyłbym ten, który na Queen's nazywaliśmy "Diabelskim Artykułem" -- obowiązkowy do napisania na czwartym roku. Wiesz, ten, w którym, trzeba udowodnić, że P = NP?

Nowa Dziewczyna: Napisałam go! Udowodniłam, że P = NP! Byłam jedną z najlepszych w grupie, a profesor pokazywał mój artykuł jako przykład!

Joey: Udowodniłaś, że P = NP?

Nowa Dziewczyna: Tak!

Joey: Mam cię!

Biedny Joey. Umawianie się z szalonymi ludźmi to jedno, ale umawianie się z szalonymi ludźmi, którzy twierdzą, iż udowodnili, że P = NP to całkiem inna sprawa. Wiem, wiem, moje próby podejścia do P = NP bynajmniej nie były lepsze. Ale przynajmniej to nie ze mną się umawiasz, prawda?

NP-zupełność jest jedną z największych tajemnic w historii informatyki; być może najłatwiej będzie to zilustrować za pomocą tego komiksu xkcd:

- Poprosimy przystawki za dokładnie $15.05. - Dokładnie? Eee... - Trzymaj, te artykuły na temat problemu plecakowego powinny ci pomóc. - Słuchajcie, mam jeszcze 6 stolików, które muszę obsłużyć. - Oczywiście najszybciej jak to możliwe. Chcesz coś na temat problemu komiwojażera?

Charakterystyczną cechą problemu NP-zupełnego jest to, że otrzymanie jego optymalnych rozwiązań, korzystając z matematyki i logiki używanych obecnie, jest praktycznie niemożliwe. Oczywiście, można uzyskać rozwiązanie przybliżone, ale rozwiązanie optymalne wymaga tak wielu obliczeń, że jego otrzymanie jest nierealne nawet przy wykorzystaniu superkomputerów pracujących z, powiedzmy ... prędkością światła.

W rzeczywistości, jednym z wyróżniających się problemów informatyki, jest stwierdzenie, czy istnieją pytania, dla których jesteśmy w stanie szybko sprawdzić poprawność rozwiązania, ale które wymagają niesamowicie długich obliczeń, aby jakiekolwiek rozwiązanie uzyskać za pomocą bezpośredniej procedury. Problemy należące do klasy NPC zdają się być właśnie takiego rodzaju, ale jak dotąd nikomu nie udało się udowodnić, że którykolwiek z nich rzeczywiście jest tak trudny, na jaki wygląda, to znaczy, że naprawdę nie istnieje żaden praktyczny sposób generowania odpowiedzi przy użyciu komputera.

Wątpliwe jest, czy komukolwiek uda się kiedyś udowodnić, że P = NP, ale i tak warto umieć rozpoznawać problemy, które są NP-zupełne:

Niestety, dowodzenie wrodzonej niepodatności może być tak samo trudne jak znajdowanie efektywnych algorytmów.

Teoria NP-zupełności dostarcza wielu bezpośrednich technik dowodzenia, że dany problem jest "tak samo trudny" jak sporo innych problemów, o których już wiadomo, że takie są i z którymi eksperci zmagają się od lat. Uzbrojony w te techniki, być może mógłbyś udowodnić, że problem bandersnatcha jest NP-zupełny a następnie wkroczyć do biura swojego szefa i oznajmić:

Nie potarfię znaleźć efektywnego algorytmu, ale żadna z tych sławnych osób też nie potrafi.

Przynajmniej Twój szef zrozumiałby, że nie ma sensu Cię zwalniać i zatrudniać innego eksperta od algorytmów.

Możesz teraz spędzać więcej czasu na szukaniu efektywnych algorytmów dla szczególnych przypadków ogólnego problemu. Możesz poszukać takich algorytmów, które mimo braku gwarancji szybkiego działania, w większości sytuacji sprawują się dobrze. Albo może problem ten da się w jakiś sposób uprościć i znaleźć dla niego szybkie algorytmy, które znajdują rozwiązania spełniające jedynie część specyfikacji. Tak więc głównym zastosowaniem teorii NP-zupełności jest wspomaganie projektantów algorytmów -- kierowanie ich wysiłków w te strony, dla których prawdopodobieństwo uzyskania użytecznego w praktyce algorytmu jest największe.

Jak to często bywa w programowaniu, pierwszym krokiem jest nauczenie się na tyle, by umieć rozpoznawać sytuacje, w których masz naprawdę przechlapane.

Na nieszczęście dla Joeya, ten smutny wniosek z teorii złożoności najwyraźniej stosuje się również do kwestii randkowania.

1 komentarze:

Jacek Macuda pisze...

ale mi banan na japie wyskoczyl ;) stare dobre szalone czasy JMA vs. JMA

Prześlij komentarz

Related Posts with Thumbnails