jump to navigation

Czy można udowodnić, że P != NP? 10/09/2009

Posted by Mikołaj Morzy in nauka, teoria.
trackback

acm_logoW najnowszym numerze Communications of the ACM Lance Fortnow z Northwestern University McCormick School of Engineering prezentuje artykuł pt. „The Status of the P Versus NP Problem„. Pokazuje w nim sposoby, na jakie informatycy i matematycy próbowali „ugryźć” najsłynniejszy problem informatyki. Artykuł jest świetnie napisany i stanowi doskonałe wprowadzenie do tego fascynującego tematu. Najbardziej spodobał mi się fragment, w którym autor przedstawia potencjalne konsekwencje dowodu na to, że P=NP. Oczywiście, przestałaby natychmiast działać współczesna kryptografia, oparta głównie na infrastrukturze klucza publicznego i założeniu, że faktoryzacja ogromnych liczb na jest bardzo trudna. Ale oprócz tego czekałby nas nowy wspaniały świat:

Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I’m just scratching the surface. Learning becomes easy by using the principle of Occam’s razor—we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of  eather and earthquakes and other natural phenomenon.

I jeszcze jedno zdanie na zachętę:

A person who proves P = NP would walk home from the Clay Institute not with $1 million  check but with seven (actually six since the Poincaré Conjecture appears solved).  Don’t get your hopes up. Complexity theorists generally believe P ≠ NP and such a beautiful world cannot exist.

Artykuł jest też dostępny jako plik pdf. A jeśli artykuł Wam się podoba, koniecznie odwiedzcie blog Lance’a Fortnowa: Computational Complexity.

Komentarze»

1. Jak zarobić $1 000 000 nie ruszając się sprzed biurka? « data mining à la polonaise - 11/25/2009

[…] Problemy podane przez CMIC to nowy zestaw (powtarza się tylko problem Hipotezy Riemanna). Nie muszę dodawać, że nie są to problemy z gatunku takich, które można zabrać ze sobą do toalety zamiast sudoku. Jako informatyka cieszy mnie, że na liście znalazł się także problem P != NP (o którym pisałem już wcześniej). […]


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: