Lekce 6 - P vs NP problém a jeho důsledky
V minulé lekci, Dynamické programování, jsme si představili dynamické programování, které využívá již dříve spočítané výsledky.
V dnešním tutoriálu o teorii algoritmů se budeme věnovat problémům, pro něž dosud chybí známé polynomiální algoritmy. Ukážeme si způsoby možných řešení.
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ů s jejich případným řešením. Podíváme se hlavně na
problém P vs NP a jeho důsledek.
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:
PvsNPproblém - Týká se počítačů - Lze každý algoritmizační problém vyřešit "dobře"?- Hodgeova domněnka - Problém týkající se topologie.
- Poincarého domněnka - Tento problém se týká čtyřrozměrné koule.
- Riemannova hypotéza - Týká se rozložení prvočísel.
- Yangova-Millsova teorie - Týká se elementárních částic.
- Navierovy-Stokesovy rovnice - Rovnice popisující proudění tekutin.
- Birchova a Swinnertonova-Dyerova domněnka - Určení počtu řešení rovnic.
Z tohoto seznamu v roce 2003 byla dokázána pouze Poincarého domněnka ruským matematikem Grigorijem Perelmanem.
Jeden z problémů ze seznamu, P vs NP problém, se
týká teoretické informatiky. Za jeho vyřešení je přislíbena odměna
jednoho milionu dolarů.
Co je P vs NP
problém?
Zjednodušeně řečeno, P vs NP problém je
otevřená otázka: Existuje efektivní řešení na úlohy,
které zatím neumíme efektivně řešit?
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. Použijeme např. Quick sort (více v lekci Quick sort kurzu Třídicí/řadicí algoritmy).
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é. Převést ale 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í (více v kurzu Kryptografie). 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, dají polynomiálně vyřešit.
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.
P vs NP problémy
Podívejme se na tyto dva grafy:
Levý graf počítá s tím, že pro NP problémy
neexistuje nějaký dobrý algoritmus. Naopak ten vpravo
počítá 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.
Praktický příklad
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.
Na 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é a 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 s různými 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ů
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. 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čí.
Problém baťohu
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 baťohem.
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. 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í. 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.
V následujícím kvízu, Kvíz - Teorie algoritmů, si vyzkoušíme nabyté zkušenosti z kurzu.
