Je P to isté čo NP?

Takzvaný P vs NP problém – jeden zo siedmich miléniových problémov – je problémom o problémoch. Tento dodnes nevyriešený problém sa pritom týka problémov dávno vyriešených, a to dokonca problémov, ktorých riešenie je v určitom zmysle celkom jednoduché. Také jednoduché, že ho zvládnu aj počítače bez štipky rozumu a invencie.

To, že počítač dokáže vyriešiť nejaký problém, znamená v skutočnosti to, že človek je schopný napísať nejaký algoritmus, ktorý daný problém rieši. Tento algoritmus napíše vo forme počítačového programu a nakŕmi počítač týmto programom a vstupnými dátami, ktoré definujú daný problém. Počítač potom postupuje presne podľa programu a na konci vypľuje riešenie problému. Také jednoduché to je. 

Lenže až také jednoduché to zas nie je. Je tu jedna zložitosť, ktorú informatici nazývajú celkom priliehavým termínom – hovoria jej „zložitosť“. Pod zložitosťou rozumejú (zhruba povedané) čas, ktorý počítač potrebuje na vyriešenie problému. A ten môže byť rozumne krátky alebo šialene dlhý.

Písmenom P označujú informatici (počítačoví vedci) triedu problémov, na ktorých vyriešenie potrebujú počítače rozumne krátky čas. Také problémy sú nielen teoreticky, ale aj prakticky riešiteľné pomocou počítačov – to P si môžeme predstavovať ako prvé písmeno slova „prakticky“ (v skutočnosti je to prvé písmeno slova „polynomiálny“, ale do takých učeností sa tu púšťať nebudeme).

Ak sa napríklad chystáme na výlet autom z Bratislavy na Bojnický zámok, stačí zadať do počítača tieto dve miesta a počítač nájde v databáze ich vzdialenosť. Ak chceme ísť z Bojníc do Čachtíc, potom na Beckov, na Oravský hrad a nakoniec na Spišský hrad počítač nájde celkovú vzdialenosť tiež veľmi rýchlo. Ak by sme si chceli urobiť výlet po všetkých slovenských hradoch a zámkoch, pričom by sme mali dopredu jasné, v akom poradí ich chceme navštíviť, potom by nájdenie celkovej vzdialenosti trvalo asi 30-krát dlhšie, ale stále by to počítač zvládol ľavou zadnou. A to je práve kľúčová charakteristika problémov typu P: 

pri náraste veľkosti problému (počet hradov zámkov) rastie čas potrebný na ich riešenie rozumným spôsobom.

Typickým príkladom problému, ktorý nie je typu P, čiže pri ktorom je nárast času s nárastom veľkosti problému nerozumný, je zdanlivo drobná modifikácia predchádzajúceho problému. Prestavme si, že by sme chceli navštíviť všetky slovenské hrady a zrúcaniny (je ich vyše 150), ale nemali by sme dopredu stanovené poradie, v ktorom ich chceme navštíviť. Celková dĺžka cesty je pri každom poradí iná a my by sme od počítača mohli chcieť, aby nám vypočítal celkovú dĺžku cesty pre všetky možné poradia. Koľko by mu to trvalo?

Počet možných poradí, v ktorých by sme ich mohli navštvíviť, je 150! (slovom stopäťdesiat faktoriál) a to je číslo s vyše 260 ciframi. Ak by počítač za jednu sekundu preskúmal hoci aj miliardu možných poradí, čas behu programu v sekundách by stále bol vyjadrený číslom s 251 ciframi. No a to naozaj nie je rozumný čas. Len na porovnanie: vek vesmíru v sekundách je 18-ciferné číslo.

Čo má teda človek robiť, ak chce nájsť najkratšiu okružnú cestu po slovenských hradoch? Nechať počítač vygenerovať dĺžky všetkých možných ciest, a potom medzi nimi vybrať tú najkratšiu je zjavný nezmysel. A čo tak vymyslieť program, na základe ktorého by počítač sám našiel najkratšiu cestu?

Problém nájdenia najkratšej cesty, známy pod menom problém obchodného cestujúceho, už desiatky rokov zamestnáva informatikov, ktorí sa márne snažia nájsť spôsob, ako ho rýchlo riešiť. Už sme si povedali, že postupné prebratie všetkých možností je prakticky nemožné, ale to neznamená, že neexistujú nejaké lepšie postupy. Existujú? Ale áno, poznáme aj lepšie spôsoby, ako túto úlohu riešiť. Ale aj tie najlepšie by pre veľký počet hradov vyžadovali kozmické časy.

Podobných problémov existuje veľa. Nielen dovolenkári by radi optimálne plánovali svoje návštevy hradov. Letecké spoločnosti potrebujú rozvrhovať lietadlá a posádky na jednotlivé lety s dodržaním všetkých predpisov Európskej únie. Nadšenci počítačových hier tetris, míny (minesweeper) a iných by možno chceli mať počítačových súperov, ktorí za niečo stoja. Biológovia by potrebovali určovať trojrozmerný tvar proteínov alebo evolučné vzťahy biologických druhov. Tajné služby by chceli vedieť rozkódovať tajné správy svojich oponentov. Nuž ale v žiadnom z týchto prípadov nevieme napísať program, ktorý by zaručene problém riešil v rozumne krátkom čase.

Všetky tieto problémy majú spoločnú ešte jednu vlastnosť, ktorú si ilustrujeme znova na probléme obchodného cestujúceho. Predstavme si, že nechceme nutne nájsť najkratšiu trasu cez všetky hrady, ale iba zistiť, či je existuje trasa s dĺžkou najviac 1 000 kilometrov. Aj to je ťažký problém, pre ktorý nepoznáme rozumne rýchly algoritmus. Ale ak nám kolega navrhne nejakú trasu, ľahko overíme, či jej dĺžka je naozaj do 1 000 km (takáto „skúška správnosti“ patrí do triedy P). A práve táto vlastnosť definuje problémy typu NP: problémy s ľahkou skúškou správnosti tvoria triedu NP. 

Keď sa vedcom nepodarilo zostrojiť program, ktorý by problém obchodného cestujúceho dostatočne rýchlo riešil, pokúšali sa aspoň dokázať, že sa to lepšie jednoducho nedá. Ani to sa im však zatiaľ nepodarilo. Navyše, problémov podobného typu je veľa. Majú spoločné toto:  nevieme dokázať, že patria do triedy P, ale ani to, že do nej nepatria.

Miliónová otázka Clayovho inštitútu sa pýta práve na toto: sú triedy P a NP rovnaké alebo nie? Ak by boli rovnaké, znamenalo by to, že každý problém v triede NP vrátane problému obchodného cestujúceho, vieme riešiť na počítači v rozumne krátkom čase. Naopak, ak sa P nerovná NP, vedeli by sme, že naša doterajšia neschopnosť tieto problémy rozumne vyriešiť vyplýva z toho, že to jednoducho nie je možné. 

Väčšina informatikov predpokladá, že P sa nerovná NP. Dôvodom je ďalšia pozoruhodná vlastnosť problémov, o ktorých tu bola reč (obchodný cestujúci, optimalizácia prevádzky leteckých spoločností, hry tetris a minesweeper, dešifrovanie a stovky ďalších). Každý z týchto problémov má tú vlastnosť, že jeho vyriešením by sme vyriešili zároveň aj všetky ostatné (tejto vlastnosti sa hovorí NP-úplnosť). Pre každý z nich totiž informatici dokázali, že rozumne rýchly algoritmus na jeho riešenie by sa po určitej modifikácii dal použiť na všetky ostatné.

A prečo teda informatici vo všeobecnosti neveria tomu, že P = NP. Nuž preto, lebo sa už desiatky rokov neúspešne pokúšajú nájsť rozumne rýchle algoritmy pre stovky NP-úplných problémov. Mnohé z týchto problémov sú prakticky extrémne dôležité a pri hľadaní účinných algoritmov na ich riešenie bolo vyvinuté enormné úsilie. Nedá sa čudovať, že po všetkom tom úsilí si informatici nevedia celkom dobre predstaviť, že sa tieto problémy dajú riešiť rozumne rýchlo – a to dokonca všetky jedným šmahom.

Zo všetkých miléniových problémov je tento (hádam ešte spolu s Navier-Stokesovou rovnicou) najpraktickejší. To neznamená, že bez jeho vyriešenia si nevieme s prakticky dôležitými úlohami poradiť. Netreba hádzať flintu do žita ani počítač do kontajnera. Pre mnohé problémy vieme riešiť ich mierne jednoduchšiu verziu. Napríklad v prípade hradov vieme rýchlo nájsť najkratšiu trasu, ktorá najskôr prejde Slovensko raz z východu na západ, a potom nazad zo západu na východ. Takisto existujú programy, ktoré pre problém obchodného cestujúceho nájdu trasu, ktorá je najviac o 50 percent dlhšia od tej najlepšej.

Vyriešenie problému „P = NP?“ by však znamenalo obrovský krok z teoretického aj praktického hľadiska. Je to nesmierne dôležitý a zároveň extrémne zaujímavý problém. Bez ohľadu na milión dolárov.