6. diel - P vs NP problém a čo z neho vyplýva

V minulej lekcii, Dynamické programovanie , sme si predstavili programovací techniku, ktorá odstráni zdĺhavé a pomalé výpočty vecí, ktoré sme už vypočítali.

V minulých lekciách sme sa pozerali na to, ako algoritmizační problémy efektívne riešiť. Ponúka sa otázka, či ide každý problém efektívne riešiť alebo či sú problémy, ktoré riešiť efektívne nemožno. Táto téma je veľmi komplexná, takže do neho v tomto tutoriálu iba nahliadneme niekoľkými príkladmi ťažkých problémov a ako ich prípadne riešiť. Pozrieme sa hlavne na problém P vs NP a čo z neho vyplýva.

7 problémov tisícročia

V roku 2000 bolo vyhlásené tzv. 7 problémov tisícročia. Jedná sa o matematické problémy, ktoré sú považované za naozaj ťažké a ktoré majú hlboký vplyv na dianie okolo nás. Sú to:

1. P vs NP problém - Týka sa počítačov - Možno každý algoritmizační problém vyriešiť "dobre"?
2. Hodgeova domnienka - Problém týkajúci sa topológia
3. Poincarého domnienka - Tento problém sa týka štvorrozmerné gule a zaujímavosťou je, že je už ako jediný z tohto zoznamu dokázaný
4. Riemannova hypotéza - Týka sa rozloženie prvočísel
5. Yangova-Millsová teória - Týka sa elementárnych častíc
6. Navierovy-Stockesove rovnice - Rovnica popisujúca prúdenie tekutín
7. Birchova a Swinnertonova-Dyerova domnienka - Určenie počtu riešenie rovníc

Jeden z problémov sa teda týka teoretickej informatiky a to je hneď prvý P vs NP problém. Za jeho vyriešenie je prisľúbená odmena jedného milióna dolárov, takže berme tento článok aj ako návod, čo riešiť vo voľnom čase:)

Čo je P vs NP problém?

Zjednodušene povedané, P vs NP problém je otvorená otázka, či na úlohy, ktoré zatiaľ nevieme efektívne riešiť, vôbec existuje efektívne riešenie.

P problémy

Vieme, že niektoré problémy vieme riešiť Polynomiální dobre (teda s časovou zložitosťou, ktorá nie je exponenciálny). Keď chceme zoradiť poľa, nebudeme jeho prvky náhodne prehadzovať, až sa trafíme do kombinácie, kedy idú prvky za sebou, ale použijeme napr. Quick sort. Tieto problémy nazývame polynomiálnej problémy, skrátene P problémy.

NP problémy

Tiež vieme, že niektoré problémy sú ťažké. Napr. overiť heslo je ľahké, ale previesť overovací odtlačok hesla späť na pôvodnú heslo, teda prelomiť jeho bezpečnosť, v súčasnosti efektívne nemožno a môžeme ho len hádať. Na tom je napríklad postavená počítačová bezpečnosť a šifrovanie. Rozlúštenie kľúče a správy trvá exponenciálne dlho. Napriek tomu je otázka, či sa aj ťažké problémy, na ktoré zatiaľ nie je známy polynomiálnej algoritmus, nedajú polynomiálnej vyriešiť, len sme neprišli na to ako. Tieto problémy nazývame nedeterministickej polynomiálnej problémy, skrátene NP problémy.

NP-úplné problémy

Do tejto tretej kategórie patria tie NP problémy, na ktoré sú ostatní NP problémy prevoditeľné. To znamená, že ak by sme vedeli riešiť nejaký NP-úplný problém, tak každý ďalší NP problém by bol zložitejší najviac toľkokrát, ako drahý je prevod medzi týmito dvoma problémami. Príklady si ukážeme nižšie. Teoreticky ide teda "len" o to, naučiť sa riešiť NP-úplné problémy ao tom, či to dá. Zvyšok problémov by sme na ne previedli.

Kategória problémov by sme mali zavedené, aj keď to samozrejme nie sú jediné množiny problémov, sú aj problémy s exponenciálny potrebou miesta, faktoriál ... To je však ďaleko nad rámec tejto lekcie:)

P vs NP problémy

Na obrázku nižšie sú 2 grafy. Ten vľavo počíta s tým, že pre NP problémy neexistuje nejaký dobrý algoritmus. Ten vpravo počíta naopak s tým, že lepšie riešenie nájsť možno, len ho ešte nepoznáme:

Väčšina ľudí sa prikláňa k názoru, že neexistujú polynomiálnej algoritmy pre triedu NP. Teda, že problémy, ktoré nevieme riešiť dnes, nebudú pravdepodobne vedieť riešiť ani ľudia v budúcnosti. Predstavme si však, že by sa P skutočne rovnalo NP a bolo by možné objaviť polynomiálnej algoritmus, ktorý by rozlúštil komunikáciu medzi bankou a klientom ... Peniaze by už neboli v bezpečí a celý systém by sa mohol zrútiť. A druhú stranu sa zatiaľ ukazuje, že by to platiť nemuselo, ale dôkaz ešte čaká na svojho objaviteľa:)

Ukážky problémov

Poďme sa teda vrhnúť na niekoľko populárnych problémov, ktoré nevieme riešiť. Problémy sú zadané tak, aby boli laicky dobre pochopiteľné, ale sú prevoditeľné na reálne problémy v bezpečnosti a ďalších odvetviach informatiky.

Problém obchodného cestujúceho

Najznámejšie NP-úplný problém je nasledujúci. Máme niekoľko miest, rôzne vzdialenosti medzi nimi a chudáka obchodného cestujúceho, ktorý musí navštíviť všetky mestá. Rád by vedel, akú najkratšiu vzdialenosť treba uraziť, teda kadiaľ sa vydať, aby cez žiadne mesto nejazdil 2x.

Tento problém si nebudeme pliesť s problémom hľadania najkratšej cesty v grafe, ktorá sa hľadá vždy iba medzi dvoma vrcholmi a jedná sa o známy P problém.

Matematicky sa úloha obchodného cestujúceho definuje tak, že hľadáme Hamiltonskou kružnicu minimálnej dĺžky. To je kružnica, ktorá prejde všetkými vrcholmi grafu bez opakovania (okrem štartu / cieľa). (Myslíme samozrejme kružnici z hľadiska teórie grafov, nie, že budeme zapichovať kružidlo do mapy:) )

Ako taký problém riešiť?

Ak máme malý počet miest, môžeme použiť hrubú silu (brute-force) a vyskúšať všetky možné variácie miest. To je však pre dáta okolo 100 miest úplne nepoužiteľné, presnejšie príliš pomalé. Je možné použiť niekoľko tzv. Heuristiky.

Heuristiky sú akési snahy o urýchlenie algoritmu za cenu získania riešenie, ktoré často nie je ideálne (ak nemáme zrovna šťastie), ale je dostatočne dobré. Spomenieme si tu pre ilustráciu dve heuristiky - pomoc najbližšieho suseda a hladný algoritmus.

Najbližší sused

Obchodný cestujúci začne v ľubovoľnom meste. Potom sa vydá po najkratšej možnej ceste do ďalšieho mesta a nakoniec, až prejde všetky mestá, sa vráti späť.

Hladný algoritmus

Na situáciu môžeme ísť aj inak. Obchodný cestujúci si najskôr zoradia všetky dvojice miest od najmenších podľa veľkosti. Nakoniec sa dvojica skladajú do grafu. Ak by náhodou nastal niekde cyklus, hrana sa preskočí.

Ďalšie NP ťažké úlohy

Podobných úloh existuje veľa, uveďme si ďalší najznámejšie.

Problém batohu

Predstavme si, že sme horskí zásobovači a v chladných ránach šplháme do odľahlých horských hotelov s našim batohom. Majitelia sú tak zúfalí, že kúpi všetko, čo tam prinesieme. Poznáme svoje medze a povieme si, že viac ako určitý počet kíl na chrbát nevezmeme, nechceme sa zničiť. Inak máme voľné pole pôsobnosti.

Problém znie takto: Máme n vecí a každá z nich má nejakú hmotnosť a nejakú cenu. Chceme maximálny možný súčet cien jednotlivých predmetov, aby ich hmotnosť neprekročila stanovenú nosnosť.

Možná heuristika

Môžeme si predmety zoradiť zostupne podľa pomeru cena / váha a postupne pridávať. Výsledok však nebude na prvé pokusy ideálne.

Problém dvoch lúpežníkov

Máme dva lupiča, ktorí sa vlámali do domu. Ukradli televíziu, rádio, počítač, sošku z Indie, drahé víno a niekoľko lentiliek. Radi by si lup rozdelili rovným dielom, aby nikto neprišiel skrátka, tj. Aby si rozdelili predmety tak, aby sa ich celkovej sumy rovnali (resp. Aby boli čo najrovnejší).

Hladné riešenie

Opäť si môžeme trochu pomôcť heuristikou. Môžeme skúsiť pridávať najhodnotnejší predmet tomu lúpežníkom, ktorý má menej.

Problém kľučky v grafe

Máme nejaký graf a hľadáme najväčšie kľučku, tj. Úplný podgraf, čiže graf, kde každý vrchol súvisí s každým.

Problém najväčšie nezávislé množiny

Máme nejaký graf a hľadáme najväčšou nezávislou množinu, tj. Množinu vrcholov, medzi ktorými nevedie hrana.

Prevoditeľnosť problému

Pozrieme sa teraz na to, či je možné efektívne nejaký problém previesť na iný. Problém kľučky v grafe je aj štýlom písania veľmi podobný najväčšie nezávislé množine. Išlo by tieto problémy na seba preniesť? Stačí prehodiť hrany za nehraný az problému hľadania kľučky sa stane problém nájdenie najväčšie nezávislé množiny. Ako je však tento prevod rýchly? Nemôže sa stať, že sám prevod bude trvať exponenciálne dlho? Ak áno, potom na seba nie sú problémy prevoditeľné. Tu to však bude závisieť len na reprezentáciu hrán grafu a ak budeme si ich reprezentovať v matici, potom všetky 0 vymeníme za 1, a 1 za 0. Táto operácia bude polynomiálnej a budeme chcete efektívne vedieť riešiť problém kľučky, vyriešime aj problém nezávislé množiny.

Záver - K čomu to riešiť?

Prečo by sme sa vlastne mali týmito problémami zaoberať? Často sa totiž dostaneme do situácie, kedy riešenie problému trvá príliš dlho. Nie je žiadny návod pre vymýšľanie heuristika, či nejakých optimalizáciou, ale znalostí problémov, ktorí už pred nami ľudia riešili, môžeme sami nájsť prekvapivo pekné a elegantné riešenie problémov, ktoré ostatní riešia hrubou silou.

V nasledujúcom kvíze, Kvíz - Teória algoritmov, si vyskúšame nadobudnuté skúsenosti z kurzu.