Největší problém v informatice: P versus NP

Existuje sedm matematických problémů, které byly označeny za tak těžké a zajímavé, že je Clayův matematický institut označil jako problémy tisíciletí a za vyřešení každého z nich dostane řešitel odměnu jeden milion dolarů. Jeden z problémů se dotýká také informatiky a nazývá se problém P versus NP. Pojďme si vysvětlit, o čem vlastně tento problém je.

Jako takhle. Nenalhávejme si, že bude jednoduché to vysvětlit. Je to přeci jenom problém tisíciletí. Takže si běžte uvařit dobrý zelený čaj 🍵 a pojďme na to. Nejprve si ukážeme čtyři různé problémy ze světa informatiky a algoritmů. Problémy si analyzujeme a ukážeme si, jaký mají vztah s písmenky P a NP.

Problém č. 1: Nalezení nejmenšího čísla

P vs. NP se dotýká algoritmů a jejich složitosti. Představte si, že bych před vás vysypal sto papírků, na každém z nich by bylo napsáno jedno číslo, a chtěl bych po vás, abyste mi našli papír, na kterém je napsáno to nejmenší číslo. Jak dlouho vám to bude trvat?

Půl minuty? Dvě minuty?

To jsou časové jednotky, které nás v teoretické informatice zase tak moc nezajímají. Co nás zajímá je spíše počet operací. Mohli bychom se tak zeptat trochu jinak: kolik papírků musím zkontrolovat, abych měl jistotu, že jsem našel nejmenší číslo? Odpovědí je, že musím zkontrolovat všechny papírky — protože to nejmenší číslo může být na tom posledním papírku. Když před vás hodím sto papírků, musíte zkontrolovat sto papírků. Když vám jich hodím tisíc, musíte jich zkontrolovat tisíc. Obecně, když před vás hodím n papírků, musíte zkontrolovat n papírků.

Tomuto říkáme složitost algoritmů. Pokud před vás hodím n papírků a vy musíte udělat n operací, abyste našli nejmenší číslo, znamená to, že tento algoritmus hledání nejmenšího čísla má složitost n, čemuž také říkáme lineární složitost, protože složitost je popsána lineární funkcí.

Dobře, prošli jste sto papírků a oznámili jste, že nejmenší číslo je 17. Jakým způsobem si můžu zkontrolovat, že říkáte pravdu? Neexistuje žádný jiný způsob než zase projít všechny papírky a zkontrolovat, že na žádném z nich není menší číslo. Tedy, vy se musíte podívat na n papírků, abyste našli nejmenší číslo a já, když to chci zkontrolovat, musím udělat to samé. Složitost ověření výsledku je tedy také n, lineární složitost.

Existují algoritmy, u kterých je jednodušší zkontrolovat výsledek než ten výsledek nalézt?

Problém č. 2: Součin páru

Představte si, že před vás vysypu dvě stejně velké hromádky papírků, na každém papírku je zase jedno číslo. A teď bych po vás chtěl, abyste našli číslo z hromádky A a číslo z hromádky B tak, aby jejich součin dával číslo 918. Pro příklad, mějme takové hromádky čísel:

$$\begin{eqnarray} A &=& \left\{49, 11, 32, 54, 15\right\}\\ B &=&\left\{17, 64, 74, 61, 21\right\} \end{eqnarray}$$

Jakým způsobem můžeme nalézt dvojici čísel tak, aby jejich součin byl rovný 918? No, můžeme zkrátka vyzkoušet všechny možnosti. Kolik jich bude? Celkem hodně, bude jich 25. Začneme tím, že vynásobíme první číslo z hromádky A, tj. číslo 49, s každým číslem z hromádky B:

$$\begin{eqnarray} 49\cdot17&=&833\\ 49\cdot64&=&3136\\ 49\cdot74&=&3626\\ 49\cdot61&=&2989\\ 49\cdot21&=&588\\ \end{eqnarray}$$

Žádná dvojice čísel nevede na 918. Zkusíme tedy totéž se zbylými čísly z hromádky A, tj. dalších pět párů pro číslo 11, dalších pět párů pro číslo 32, dalších pět párů pro 54 a posledních pět párů pro 15. Celkem tak můžeme vyzkoušet 25 párů čísel. Nakonec zjistíme, že 54 · 17 = 918.

Jaká je složitost tohoto algoritmu? Bude nás zajímat, kolik párů čísel jsme museli vynásobit. Obě hromádky obsahovaly pět lístečků a my jsme museli zkusit každé z pěti čísel z první hromádky s každým z pěti čísel z druhé hromádky. Celkem jsme zkusili 5 · 5 = 25 kombinací. Kdybych před vás hodil dvě hromádky o 10 papírcích, museli byste zkusit 10 · 10 = 100 kombinací. Když to zobecníme, hodím-li před vás dvě hromádky o n papírcích, musíte vyzkoušet n · n = n² kombinací.

Řekneme, že tento náš algoritmus má složitost n², kvadratickou složitost, protože ji popisuje kvadratická funkce.

Jak složité ale bude zkontrolovat výsledek? Pokud mi odpovíte, že 54 a 17 jsou čísla, jejichž součin dává 918, nemusím už procházet všechny dvojice čísel z obou hromádek jako jste to museli dělat vy. Stačí mi, když si vynásobím tento jeden pár 54 · 17 a budu vědět, jestli máte pravdu nebo ne. Takže zatímco na vyřešení tohoto problému je potřeba vypočítat až n² součinů, na ověření stačí vypočítat pouze jeden součin. Ověření má tedy konstantní složitost 1.

Tím se tato úloha výrazně liší od té předchozí, kde jsme potřebovali stejně kroků na samotný výpočet a na následné ověření.

Tato úloha je také řádově složitější než ta předchozí. Když bych před vás vysypal deset tisíc papírků a chtěl najít nejmenší číslo, asi byste ho byli schopni za jeden den najít. Kdybych před vás ale vysypal dvakrát deset tisíc papírků a nechal vás hledat součin, museli byste zkontrolovat deset tisíc krát deset tisíc součinů, což je sto milionů výpočtů. I kdybyste zkusili jeden součin za sekundu, trvalo by vám to asi tři roky.

Problém č. 3: Součet podmnožiny

Pojďme si ukázat třetí problém. Tentokrát před vás vysypu dvanáct papírků s čísly a chtěl bych po vás, abyste našli libovolný počet papírků, jejichž součet dává nula. Pro příklad:

$$ A = \left\{24,-69{,}1,-15,-76,-60{,}16,-83{,}48,-22{,}54,-47\right\} $$

Vyberte z těchto čísel libovolnou skupinu čísel, jejichž součet dává 0. Například čísla

$$24+48-69+1$$

dávají součet 4 a nejsou tak správnou odpovědí. Správnou odpovědí je skupina čísel… a víte co? Zkuste si to najít sami za domácí úkol 😉. Existuje jediná skupina čísel, jejichž součet dává 0. Alespoň si vyzkoušíte, jak je tento problém těžký.

Teď potřebujeme znát složitost tohoto problému. Samotný výpočet už není úplně triviální a bude spíš pro fajnšmekry. Pokud vás tedy zajímá, jak lze vypočítat složitost tohoto problému, pokračujte ve čtení. Jinak můžete přeskočit k další kapitole. ⏩

Jakým způsobem tedy můžeme nalézt skupinu čísel, jejichž součet dává 100? No, musíme zkrátka vyzkoušet všechny možné kombinace čísel. Musíme vyzkoušet všechny dvojice čísel, všechny trojice, čtveřice, pětice atd. a musíme u každé skupiny ověřit, jestli jejich součet dává nula. Kolik takových kombinací existuje?

Pojďme si to ukázat na menší množině čísel. Kolik různých skupin čísel, neboli podmnožin, můžu vytvořit z trojice čísel B = {5, 7, 9}? Je jich celkem osm:

$$\begin{eqnarray} B_1&=&\left\{\right\}\\ B_2&=&\left\{5\right\}\\ B_3&=&\left\{7\right\}\\ B_4&=&\left\{9\right\}\\ B_5&=&\left\{5{,}9\right\}\\ B_6&=&\left\{5{,}7\right\}\\ B_7&=&\left\{7, 9\right\}\\ B_8&=&\left\{5{,}7,9\right\}\\ \end{eqnarray}$$

Všimněte si, že jsme započítali i prázdnou podmnožinu B₁. Není to teď moc užitečné, ale pro pořádek jsme ji tam nechali. Abychom si zjednodušili výpočet, přiřadíme každé podmnožině binární vektor. Binární vektor je prostě jen posloupnost nul a jedniček, třeba 00101010. My budeme pracovat s binárními vektory o délce tři. Vektor přiřadíme tak, že 101 přiřadíme podmnožině, která obsahuje „první a třetí číslo z původní množiny, ale ne druhé číslo“, tj. množině {5, 9}. Vektor 110 přiřadíme podmnožině, která obsahuje „první a druhé číslo z původní množiny, ale ne třetí“, tj. množině {5, 7} atp.

$$\begin{eqnarray} B_1=\left\{\right\}&\rightarrow&000\\ B_2=\left\{5\right\}&\rightarrow&100\\ B_3=\left\{7\right\}&\rightarrow&010\\ B_4=\left\{9\right\}&\rightarrow&001\\ B_5=\left\{5{,}9\right\}&\rightarrow&101\\ B_6=\left\{5{,}7\right\}&\rightarrow&110\\ B_7=\left\{7, 9\right\}&\rightarrow&011\\ B_8=\left\{5{,}7,9\right\}&\rightarrow&111\\ \end{eqnarray}$$

Vidíme, že každá podmnožina má právě jeden binární vektor o délce tři. A každý binární vektor o délce tři odpovídá právě jedné podmnožině. Tedy, pokud vypočítáme, kolik existuje různých binárních vektorů o délce n, získáme počet různých kombinací, které umíme poskládat, pokud máme na vstupu n různých čísel. Pojďme si to tedy spočítat.

Binární vektory o délce jedna existují dva: 0 a 1.

Binární vektory o délce dva získáme tak, že vezmeme všechny binární vektory o délce jedna a na konec každého vektoru přidáme 0: získáme vektory 00 a 10. Znovu vezmeme všechny vektory o délce 1 a přidáme na konec 1: 01 a 11. Tím jsme získali všechny vektory o délce 2: 00, 01, 10 a 11.

Binární vektory o délce tři získáme tak, že vezmeme všechny binární vektory o délce dva a na konec přidáme nulu: 000, 010, 100 a 110 a jedničku: 001, 011, 101 a 111.

A tak dále pro každou další délku. Vidíme, že když zvýšíme délku binárního vektoru o jedna, vzroste počet různých binárních vektorů na dvojnásobek. Pro délku vektoru čtyři bychom tedy získali celkem 2 · 2 · 2 · 2, což je 16, různých kombinací.

Obecně můžeme odvodit, že máme-li množinu M, která obsahuje n prvků, potom počet všech podmnožin této množiny M je roven počtu všech různých binárních vektorů o délce n a to je rovno

$$\underbrace{2\cdot2\cdot\ldots\cdot2}_{n-\mbox{krát}}=2^n$$

2ⁿ nebo n² — není to jedno? Bába nebo sníh 🤷‍♂

Existuje tedy 2ⁿ různých podmnožin, které můžeme vytvořit z množiny o n číslech. V našem případě máme n = 12 čísel a musíme tedy zkontrolovat 2¹² různých kombinací, což je 4096 kombinací. Řekneme, že tento problém má složitost 2ⁿ, exponenciální složitost, protože ho popisuje exponenciální funkce.

Všimněte si, že předchozí problém měl složitost n², zatímco tento má složitost 2ⁿ. Vypadá to hodně podobně, že? Jenomže je velký rozdíl mezi tím, kdy máme exponent konstantní a když tam máme proměnnou n. Všimněte si, že když n = 4, tak dostaneme

$$\begin{eqnarray} n^2&=&4^2&=&16\\ 2^n&=&2^4&=&16 \end{eqnarray}$$

Dobře, zatím nám to vychází stejně. Co když n = 10?

$$\begin{eqnarray} n^2&=&10^2&=&100\\ 2^n&=&2^{10}&=&1024 \end{eqnarray}$$

Huh, exponenciální funkce nám vystřelila a je najednou asi desetkrát větší než kvadratická. Co dostaneme pro n = 20?

$$\begin{eqnarray} n^2&=&20^2&=&400\\ 2^n&=&2^{20}&=&1~048~576 \end{eqnarray}$$

Exponenciální složitost má pro n = 20 zhruba 2500krát vyšší hodnotu než kvadratická složitost. Vidíme tedy, že exponenciální funkce roste mnohem rychleji než kvadratická funkce. Vzpomeňte si na to, až nás zase postihne nějaká pandemie, která se bude v populaci šířit exponenciální rychlostí.

Pokud bych tedy před vás hodil dvacet papírků, museli byste zkontrolovat 1 048 576 kombinací. To je docela dost.

Jak ověříme správnost výsledku?

Jak dlouho mi bude trvat ověřit, že výsledná skupina čísel opravdu dává součet 0? To bude poměrně rychlé, prostě sečtu tuto jednu skupinu čísel a pokud bude její součet roven 0, tak jste našli správnou skupinu papírků, pokud bude součet jiný, našli jste špatnou sadu papírků.

Znovu vidíme, že zkontrolovat výsledek je řádově jednodušší než ho nalézt.

Problém č. 4: Problém obchodního cestujícího

Problém obchodního cestujícího je jedním z nejslavnějších algoritmických problémů. Zhruba řečeno, máme obchodního cestujícího, který prodává déšť. A tento obchodní cestující musí hodně cestovat, aby si na sebe vydělal. Rozhodl se proto, že navštíví každé krajské město v České republice. A protože nechce plýtvat, rozhodl se, že nalezne nejkratší možnou cestu která ho provede všemi krajskými městy v republice. A naším úkolem je takovou nejkratší cestu nalézt.

Jak můžeme tuto nejkratší cestu nalézt? Vyzkoušíme všechny možnosti.

Můžeme si to zjednodušit. Představme si, že mezi každými dvěma krajskými městy existuje právě jedna nejkratší cesta. Jakým způsobem můžeme nalézt nejkratší cestu mezi všemi městy? Krajských měst máme 14. Máme tedy 14 možností kde začít. Dejme tomu, že jsme začali v Ostravě!!! Kam se můžeme dostat z Ostravy? Teoreticky můžeme jet do jakéhokoliv jiného krajského města. Můžeme tedy vybírat z 13 zbývajících měst.

Už teď můžeme spočítat, že máme celkem 14 · 13 možností jak navštívit první dvě krajská města — máme 14 možností kde začít a pak máme na výběr ze 13 zbývajících krajských měst.

Když dojedeme do druhého města, musíme pokračovat dále. Ve dvou městech už jsme byli, takže můžeme odcestovat do jednoho ze 12 zbývajících měst. Máme tak celkem 14 · 13 · 12 možností, jak navštívit první tři města.

Až navštívíme třetí krajské město, musíme si vybrat jedno z 11 zbývajících měst, pak jedno z 10 zbývajících měst atd.

Až navštívíme všechna, zjistíme, že jsme měli na výběr celkem z

$$14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$$

možností. To vám může připomínat faktoriál, který označujeme vykřičníkem. Můžeme tak říci, že tento součin se rovná 14!:

$$14!=14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$$

a tedy existuje 14! cest, které vedou přes všechna krajská města v České republice. Je to hodně? Docela jo, protože

$$14!=87~178~291~200.$$

Obecně, pokud bychom hledali nejkratší cestu mezi n městy, museli bychom zkusit n! různých cest. Složitost toho řešení tak je n!.

Jak bychom ověřili, že jsme nalezli správný výsledek? Kdybyste mi řekli, že nejkratší cesta je z Plzně do Ostravy, pak do Brna atd., jak můžu ověřit, že mi říkáte pravdu? No, dost těžko 🤷‍♂. Protože když se na tu cestu podívám, nemám jak snadno ověřit, jestli je zrovna tato cesta nejkratší. Musím vlastně celý výpočet provést znova. Složitost ověření výsledku má tak také složitost n!.

Třídy P a NP

Představili jsme si čtyři problémy a algoritmy, které je řeší a analyzovali jsme, jak složité je nalézt řešení a jak složité je zkontrolovat toto řešení. Můžeme si to shrnout v této tabulce:

Nyní si naše problémy rozdělíme do dvou skupin. První skupinu budou tvořit problémy, které jsou jednoduché na vyřešení. Jsou to problémy, které lze vyřešit se složitostí n nebo n² nebo n³ nebo n⁴ atd. Protože výrazy jako n² nazýváme polynomy, označujeme tuto třídu problémů písmenem P. Říkáme tedy, že třída P obsahuje problémy, které lze vyřešit v polynomiálním čase (= mají složitost třeba n² nebo n⁷). Obecně jsou to problémy, které lze vyřešit více méně jednoduše.

Do třídy P tak patří problém č. 1, nalezení nejmenšího čísla, protože ten má složitost řešení n a pak tam patří problém č. 2, součin páru, protože jeho složitost řešení je n², což jsou obojí polynomy.

Druhou třídou je třída NP. Ta obsahuje problémy, které lze ověřit v polynomiálním čase. Do třídy NP tak patří všechny problémy, až na ten poslední. Problém obchodního cestujícího nelze ověřit v polynomiálním čase. Předchozí tři problémy lze ověřit v polynomiálním čase.

Problém obchodního cestujícího nelze vyřešit, ani ověřit v polynomiálním čase. Pro problém obchodního cestujícího bychom tak potřebovali ještě další třídu, která by obsahovala ještě těžší problémy. Tato třída existuje, ale pro nás není v tuto chvíli zajímavá.

Je zřejmé, že třída P je podmnožinou třídy NP. Tedy že každý problém, který je ve třídě P, je zároveň ve třídě NP. Dává to smysl — pokud jsme schopni nějaký problém vyřešit v polynomiálním čase, jsme schopni výsledek i ověřit v polynomiálním čase.

Problém P vs. NP

A platí to i opačně? Je každý problém ze třídy NP zároveň také ve třídě P? Tedy, pokud existuje způsob, jak ověřit výsledek problému v polynomiální čase, existuje také algoritmus, který by daný problém řešil v polynomiálním čase?

Pro příklad, víme, že jsme schopni ověřit výsledek problému č. 3, součet podmnožiny, v polynomiálním čase. Ale na jeho vyřešení jsme použili algoritmus, který není polynomiální, použitý algoritmus má exponenciální složitost 2ⁿ. Víme ale jistě, že pro tento problém neexistuje žádný algoritmus s polynomiální složitostí?

Nevíme!

Klidně by se mohlo stát, že pro každý problém, který lze ověřit v polynomiálním čase, existuje algoritmus, který tento problém řeší v polynomiálním čase. My to nevíme. Neumíme dokázat existenci takového algoritmu, ale neumíme ani vyvrátit existenci tohoto algoritmu.

Pokud by pro každý problém z třídy NP existoval algoritmus, který ho řeší v polynomiálním čase, znamenalo by to, že by třída NP byla vlastně rovna třídě P. Všechny problémy z třídy P by byly v třídě NP a všechny problémy z třídy NP by byly v třídě P — obě třídy by se rovnaly, byly by shodné.

Problém P vs. NP je tedy otázka, zda je třída P shodná s třídou NP, anebo zda se jedná o dvě různé třídy problémů.

Buď tedy platí P = NP, nebo platí P ≠ NP. Toto nikdo neví a pokud na to přijdete, čeká vás odměna jeden milion dolarů, nehynoucí sláva a pravděpodobně také Turingova cena, což je taková Nobelovka pro informatiky.

Co by se stalo, kdyby P = NP?

Co by se stalo, kdyby platilo, že P = NP? No, není úplně jednoduché říci, co by se stalo. Věděli bychom, že pro všechny problémy z třídy NP existuje algoritmus, který je řeší v polynomiálním čase. Například, že pro náš problém č. 3, součet podmnožiny, existuje algoritmus, který ho řeší v polynomiálním čase. Jenomže to má dva háčky:

• To, že bychom věděli, že takový algoritmus existuje, neznamená, že ho jsme schopni nalézt. Zkrátka bychom věděli, že ano, existuje algoritmus, který problém řeší v polynomiálním čase, ale neuměli bychom ho třeba ještě dalších sto let sestrojit. Je to něco podobného, jako když Albert Einstein dokázal existenci černých děr, ale přesto nám trvalo několik dalších desetiletí, než jsme dokázali pořídit první „fotografii“ černé díry.
• To, že existuje algoritmus pracující v polynomiálním čase ještě bohužel neznamená, že je rychlý. Mohli bychom nalézt algoritmus, který má složitost n¹⁰⁰. On totiž i výraz n¹⁰⁰ je polynom. Když si porovnáme složitosti 2ⁿ a n¹⁰⁰, tak zjistíme, že dokud je n relativně malé, tak algoritmus se složitostí 2ⁿ stále ještě potřebuje méně operací. Například pro n = 20 platí, že 2²⁰ = 1 048 576, zatímco výraz 20¹⁰⁰ vede na číslo, které má asi 130 číslic, což je číslo, které je o 120 řádů větší než 1 048 576. Náš polynomiální algoritmus by tak v realitě byl pomalejší než ten exponenciální. Alespoň dokud je n relativně malé.
• Pokud bychom přeci jen dokázali nalézt rychlý algoritmus pracující v polynomiálním čase, dokázali bychom spoustu problémů řešit rychleji a s větší přesností. To je samozřejmě pozitivní zpráva, ale má to i svá negativa. Existuje obor, který se spoléhá na to, že některé problémy jsou těžko řešitelné a to je kryptografie — šifrování. Mohlo by se tak stát, že by bylo řádově jednodušší prolomit současné šifry.

Intermezzo: protože jste dočetli až sem, tak vám za odměnu prozradím, že řešení problému č. 3 je 24 + 1 − 60 + 16 − 83 + 48 + 54.

Co by se stalo, kdyby P ≠ NP?

Kdyby platilo, že třídy problémů P a NP jsou různé, tak se toho zase tak moc nestane, protože to je více méně status quo. My v současné chvíli nemáme žádný algoritmus, který by řešil nějaký těžký problém z NP v polynomiálním čase a pokud by někdo dokázal, že P ≠ NP, tak by to tak zkrátka zůstalo navždy. Daleko větší senzací by byl důkaz, že P = NP.

Odkazy v popkultuře

• V jednom díle Simpsonů můžeme vidět, že se Homer dostane do jakési alternativní reality, ve které se mu zjeví, že P = NP. K vidění na youtube.com.
• Naopak ve Futuramě zase můžeme vidět, že mají ve skladu dvě složky, jednu s názvem P a druhou s názvem NP. K vidění na youtube.com.
• Druhý díl druhé série seriálu Sherlock Holmes: Jak prosté s názvem „Řešení neznámé“ se věnoval vraždě matematika, který pravděpodobně vyřešil problém P versus NP.