Lekce 6 - P vs NP problém a co z něj vyplývá

V minulé lekci, Dynamické programování, jsme si představili programovací techniku, která odstraní zdlouhavé a pomalé výpočty věcí, které jsme už vypočítali.

V minulých lekcích jsme se dívali na to, jak algoritmizační problémy efektivně řešit. Nabízí se otázka, zda jde každý problém efektivně řešit či zda jsou problémy, které řešit efektivně nelze. Toto téma je velmi komplexní, takže do něj v tomto tutoriálu pouze nahlédneme několika příklady těžkých problémů a jak je případně řešit. Podíváme se hlavně na problém P vs NP a co z něj vyplývá.

7 problémů tisíciletí

V roce 2000 bylo vyhlášeno tzv. 7 problémů tisíciletí. Jedná se o matematické problémy, které jsou považovány za opravdu těžké a které mají hluboký dopad na dění kolem nás. Jsou to:

1. P vs NP problém - Týká se počítačů - Lze každý algoritmizační problém vyřešit "dobře"?
2. Hodgeova domněnka - Problém týkající se topologie
3. Poincarého domněnka - Tento problém se týká čtyřrozměrné koule a zajímavostí je, že je již jako jediný z tohoto seznamu dokázaný
4. Riemannova hypotéza - Týká se rozložení prvočísel
5. Yangova-Millsova teorie - Týká se elementárních částic
6. Navierovy-Stokesovy rovnice - Rovnice popisující proudění tekutin
7. Birchova a Swinnertonova-Dyerova domněnka - Určení počtu řešení rovnic

Jeden z problémů se tedy týká teoretické informatiky a to je hned první P vs NP problém. Za jeho vyřešení je přislíbena odměna jednoho milionu dolarů, takže berme tento článek i jako návod, co řešit ve volném čase

Co je P vs NP problém?

Zjednodušeně řečeno, P vs NP problém je otevřená otázka, zda na úlohy, které zatím neumíme efektivně řešit, vůbec existuje efektivní řešení.

P problémy

Víme, že některé problémy umíme řešit polynomiálně dobře (tedy s časovou složitostí, která není exponenciální). Když chceme seřadit pole, nebudeme jeho prvky náhodně prohazovat, až se trefíme do kombinace, kdy jdou prvky za sebou, ale použijeme např. Quick sort. Tyto problémy nazýváme polynomiální problémy, zkráceně P problémy.

NP problémy

Také víme, že některé problémy jsou těžké. Např. ověřit heslo je snadné, ale převést ověřovací otisk hesla zpět na původní heslo, tedy prolomit jeho bezpečnost, v současné době efektivně nelze a můžeme jej jen hádat. Na tom je kupříkladu postavená počítačová bezpečnost a šifrování. Rozluštění klíče a zprávy trvá exponenciálně dlouho. Přesto je otázka, zda se i těžké problémy, na které zatím není znám polynomiální algoritmus, nedají polynomiálně vyřešit, jen jsme nepřišli na to jak. Tyto problémy nazýváme nedeterministické polynomiální problémy, zkráceně NP problémy.

NP-úplné problémy

Do této třetí kategorie spadají ty NP problémy, na které jsou ostatní NP problémy převoditelné. To znamená, že pokud bychom uměli řešit nějaký NP-úplný problém, tak každý další NP problém by byl složitější nejvýše tolikrát, jak drahý je převod mezi těmito dvěma problémy. Příklady si ukážeme níže. Teoreticky jde tedy "jen" o to, naučit se řešit NP-úplné problémy a o tom, zda to lze. Zbytek problémů bychom na ně převedli.

Kategorie problémů bychom měli zavedené, i když to samozřejmě nejsou jediné množiny problémů, jsou i problémy s exponenciální potřebou místa, faktoriály... To je však dalece nad rámec této lekce

P vs NP problémy

Na obrázku níže jsou 2 grafy. Ten vlevo počítá s tím, že pro NP problémy neexistuje nějaký dobrý algoritmus. Ten vpravo počítá naopak s tím, že lepší řešení najít lze, jen ho ještě neznáme:

Většina lidí se přiklání k názoru, že neexistují polynomiální algoritmy pro třídu NP. Tedy, že problémy, které neumíme řešit dnes, nebudou pravděpodobně umět řešit ani lidé v budoucnu. Představme si však, že by se P skutečně rovnalo NP a bylo by možné objevit polynomiální algoritmus, který by rozluštil komunikaci mezi bankou a klientem... Peníze by již nebyly v bezpečí a celý systém by se mohl zhroutit. A druhou stranu se zatím ukazuje, že by to platit nemuselo, ale důkaz ještě čeká na svého objevitele

Ukázky problémů

Pojďme se tedy vrhnout na několik populárních problémů, které neumíme řešit. Problémy jsou zadané tak, aby byly laicky dobře pochopitelné, ale jsou převoditelné na reálné problémy v bezpečnosti a dalších odvětvích informatiky.

Problém obchodního cestujícího

Nejznámější NP-úplný problém je následující. Máme několik měst, různé vzdálenosti mezi nimi a chudáka obchodního cestujícího, který musí navštívit všechna města. Rád by věděl, jakou nejkratší vzdálenost je třeba urazit, tedy kudy se vydat, aby přes žádné město nejel 2x.

Tento problém si nebudeme plést s problémem hledání nejkratší cesty v grafu, která se hledá vždy jen mezi dvěma vrcholy a jedná se o známý P problém.

Matematicky se úloha obchodního cestujícího definuje tak, že hledáme Hamiltonskou kružnici minimální délky. To je kružnice, která projde všemi vrcholy grafu bez opakování (kromě startu/cíle). (Myslíme samozřejmě kružnici z hlediska teorie grafů, ne, že budeme zapichovat kružítko do mapy )

Jak takový problém řešit?

Pokud máme malý počet měst, můžeme použít hrubou sílu (brute-force) a vyzkoušet všechny možné variace měst. To je však pro data kolem 100 měst úplně nepoužitelné, přesněji příliš pomalé. Je možné použít několik tzv. heuristik.

Heuristiky jsou jakési snahy o urychlení algoritmu za cenu získání řešení, které často není ideální (pokud nemáme zrovna štěstí), ale je dostatečně dobré. Zmíníme si zde pro ilustraci dvě heuristiky - pomoc nejbližšího souseda a hladový algoritmus.

Nejbližší soused

Obchodní cestující začne v libovolném městě. Potom se vydá po nejkratší možné cestě do dalšího města a nakonec, až projde všechna města, se vrátí zpět.

Hladový algoritmus

Na situaci můžeme jít i jinak. Obchodní cestující si nejdříve seřadí všechny dvojice měst od nejmenší podle velikosti. Nakonec se dvojice skládají do grafu. Pokud by náhodou nastal někde cyklus, hrana se přeskočí.

Další NP těžké úlohy

Podobných úloh existuje spoustu, uveďme si další nejznámější.

Problém batohu

Představme si, že jsme horští zásobovači a v chladných ránech šplháme do odlehlých horských hotelů s naším batohem. Majitelé jsou tak zoufalí, že koupí všechno, co tam přineseme. Známe své meze a řekneme si, že více než určitý počet kil na záda nevezmeme, nechceme se zničit. Jinak máme volné pole působnosti.

Problém zní takto: Máme n věcí a každá z nich má nějakou hmotnost a nějakou cenu. Chceme maximální možný součet cen jednotlivých předmětů, aby jejich hmotnost nepřekročila stanovenou nosnost.

Možná heuristika

Můžeme si předměty seřadit sestupně podle poměru cena/váha a postupně přidávat. Výsledek ovšem nebude na první pokusy ideální.

Problém dvou loupežníků

Máme dva lupiče, kteří se vloupali do domu. Ukradli televizi, rádio, počítač, sošku z Indie, drahé víno a několik lentilek. Rádi by si lup rozdělili rovným dílem, aby nikdo nepřišel zkrátka, tj. aby si rozdělili předměty tak, aby se jejich celkové sumy rovnaly (resp. aby byly co nejrovnější).

Hladové řešení

Opět si můžeme trochu pomoci heuristikou. Můžeme zkusit přidávat nejhodnotnější předmět tomu loupežníkovi, který má méně.

Problém kliky v grafu

Máme nějaký graf a hledáme největší kliku, tj. úplný podgraf, neboli graf, kde každý vrchol souvisí s každým.

Problém největší nezávislé množiny

Máme nějaký graf a hledáme největší nezávislou množinu, tj. množinu vrcholů, mezi kterými nevede hrana.

Převoditelnost problému

Podíváme se nyní na to, zda lze efektivně nějaký problém převést na jiný. Problém kliky v grafu je i stylem psaní velmi podobný největší nezávislé množině. Šlo by tyto problémy na sebe přenést? Stačí prohodit hrany za nehrany a z problému hledání kliky se stane problém nalezení největší nezávislé množiny. Jak je však tento převod rychlý? Nemůže se stát, že sám převod bude trvat exponenciálně dlouho? Pokud ano, pak na sebe nejsou problémy převoditelné. Zde to však bude záviset jen na reprezentaci hran grafu a budeme-li si je reprezentovat v matici, pak všechny 0 vyměníme za 1, a 1 za 0. Tato operace bude polynomiální a budeme-li efektivně umět řešit problém kliky, vyřešíme i problém nezávislé množiny.

Závěr - K čemu to řešit?

Proč bychom se vlastně měli těmito problémy zabývat? Často se totiž dostaneme do situace, kdy řešení problému trvá příliš dlouho. Není žádný návod pro vymýšlení heuristik, či nějakých optimalizací, ale znalostí problémů, kteří už před námi lidé řešili, můžeme sami nalézt překvapivě hezké a elegantní řešení problémů, které ostatní řeší hrubou silou.