Mezi předpověďmi pro rok 2011 se objevila i možnost, že v letošním roce dojde k definitivnímu vyřešení otázky vztahu mezi úlohami typu P a NP. Jedná se o matematický problém spadající do kategorie výpočetní složitosti. Jeho řešení má vztah např. ke kryptografii, kvantovému počítání i řešení některých výpočetně velmi náročných úloh.
Problém P vs. NP je dnes pokládán za jednu ze 6 úloh, které pro matematiky představují největší výzvu. Americký Clayův institut nabídl za řešení každé z nich částku 1 milionu dolarů (původně bylo těchto úloh 7, jedna z nich, Poincarého hypotéza, však už byla mezitím dokázána). Úloha P vs. NP se pokládá za jedinou z nich, kterou by mohl vyřešit i někdo jiný než profesionální matematik, nebo minimálně zde i my laici dokážeme alespoň pochopit zadání.
Výpočetní složitost se zabývá otázkou, jak závisí doba trvání výpočtu na velikosti vstupu. Může zde existovat například lineární vztah, často se ale po zdvojnásobení vstupních dat stává úloha mnohem obtížnější než jen dvojnásobně. Mluvíme pak třeba o polynomiálních nebo exponenciálních úlohách (přesněji řečeno, výpočetní složitost není vlastností úlohy, ale konkrétního algoritmu; když říkáme, že úloha je náročná tak a tak, myslíme tím, že neexistuje algoritmus, který by ji dokázal vyřešit rychleji – méně efektivní postupy samozřejmě existují). Na této asymetrii stojí řada postupů v kryptografii – šifrování musí být mnohem rychlejší než opačný postup, tedy dešifrování. Známým příkladem je faktorizace. Vynásobit dvě velká prvočísla jde poměrně snadno, naopak hledání rozkladu výsledného obřího čísla (to je právě ona tzv. faktorizace) je mnohem náročnější. Nebo jinak řečeno, faktorizovat je obtížné, jde ale snadno ověřit, že jsme to udělali správně.
Problém P vs. NP se týká vztahu mezi dvěma oblastmi výpočetní složitosti, mezi úlohami polynomiálními (P) a nedeterministicky polynomiálními (NP). Vesměs se předpokládá, že NP, kam patří třeba problém obchodního cestujícího, nelze řešit stejně rychle jako P a obě úlohy na sebe nejdou převést. Nikomu se ovšem nepodařilo rozdílnost ani shodu dokázat. Do kategorie NP spadá např. problém obchodního cestujícího či problém splnitelnosti, k nimž vede řada úloh např. z genetiky/bioinformatiky. Obtížnější než NP není určitě ani faktorizace. Pokud by se v rozporu s očekáváním ukázalo, že NP je shodné jako P, znamenalo by to potenciálně rychlejší lámání šifer.
Samotný problém P vs NP je už stařičký, byl zformulován v roce 1971. Proč by pro jeho řešení mohl být významný právě letošní rok? Loni totiž Vinay Deolalikar, výzkumník z laboratoří firmy HP v kalifornském Palo Altu, přišel s tím, že úlohu vyřešil. Výsledek dle něj odpovídá většinovým předpokladům, že oba typy úloh jsou různě výpočetně náročné, P se nerovná NP. Deolalikarovu práci se ovšem loni nepodařilo zkontrolovat, minimálně se ovšem pochybuje o tom, že by byla úplná. Letos bychom v tom mohli mít jasněji.
Komentátoři upozorňují, že v souvislosti s Deolalikarovou prací se utvořila celá komunita nejen profesionálních matematiků a došlo k velké aktivitě na blozích a Wikipedii; skoro jako bychom před sebou měli nový způsob fungování matematiky...
Deolalikarův pokus o důkaz je k dispozici zde.
Proč se z rozhodnutí otázky P vs. NP se ovšem nedá jednoznačně vyvodit závěr „dnešní šifry jsou/nejsou v bezpečí“, to viz např. zde.
Zdroj: New Scientist, Scienceworld.cz a další
PŘEDPLATNÉ
ČLÁNKY DO MAILU