Student World

Co se týče praktických aplikací, defaultně se stále předpokládá, že P a NP mají různou výpočetní složitost. Záleží na tom ale v praxi zase tolik? Obvykle se v této souvislosti zmiňují kvantové počítače, šifry, faktorizace…

Jenže tohle všechno s řešením otázky P vs NP zase tak moc souviset nemusí. Tak třeba faktorizace není NP úplným problémem (respektive – není dokázáno, že je to NP úplný problém, a příliš se tomu nevěří), může být i slabší (nikoliv silnější, protože lze řešit jako problém splnitelnosti). Efektivní Shorův algoritmus (viz také Cesta ke kvantovému počítači (3) – Shorův algoritmus) by prostě vedl k tomu, že by se namísto faktorizace použila v kryptografii jiná asymetrická operace, tentokrát spadající do těch NP úplných – a zde by Shorův algoritmus byl k ničemu. Navíc v praxi se třeba pro faktorizaci používají ani ne tak regulérní algoritmy, ale spíše heuristiky.

Kvantové algoritmy (Groverův) dokáží zrychlit vyhledávání (NP úplný problém) pouze tak, že výpočetní čas „stáhnou“ pod odmocninu, a Groverův postup zřejmě nelze dále zesilovat. (viz také: Cesta ke kvantovému počítači (4): Groverův prohledávací algoritmus)

To ale podle Fortnowa neznamená, že bychom měli být smutní. Problém sice v podle něj v blízké budoucnosti nevyřešíme a nemá to kupodivu ani zvláštní praktický význam, ale při celém zkoumání jakoby mimochodem přijdeme na celou řadu jiných otázek, lépe porozumíme výpočetní složitosti a vyřešíme zase další problémy (výhoda neaplikované vědy – objevy jako vedlejší produkty jiných – třeba i neúspěšných – pátrání).

Podrobnosti: ACM.org

Poznámka: P vs NP je jeden ze 7 největších problémů současné matematiky, alespoň podle Clayova ústavu. Ve výše uvedeném textu se předpokládá, že P je různé od NP: Keith Devlin v knize Problémy pro třetí tisíciletí (i většina dalších autorů populárně věděckých knih) rovněž zastávají tento názor, i když nechybí ani tipy, že problém se nakonec ukáže (goedelovsky) nerozhodnutelný a bude nějak souviset se základy samotné aritmetiky (tento názor viz např. Ian Stewart – viz úryvek Matematika roku 2050). Zajímavé je, že téměř nikdo nepočítá s možností důkazu P=NP.

Devlin mimochodem dokonce pokládá otázku P vs NP za jediný se 7 hlavních problémů současné matematiky, který by mohl vyřešit i neprofesionál, snad i jediným chytrým nápadem.

Viz také:  Jak na řešení problému, zda NP je P?, Proč je Riemannova hypotéza i problém NP úplných úloh rizikem pro kryptografii

autor Pavel Houser