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:

• P vs NP problé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.