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:
P
vsNP
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 a zajímavostí je, že je již jako jediný z tohoto seznamu dokázaný
- 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
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.
Komentáře


Zobrazeno 1 zpráv z 1.