Složitost úloh - P a NP úlohy
Třída P je třída všech rozhodovacích úloh U, pro něž existuje polynomiální algoritmus, řešící úlohy U. Rozhodovací úloha je úloha, jejímž řešením je odpověď „ano“ nebo „ne“. Každou optimalizační úlohu zle převést na rozhodovací úlohu.
Příklad - problém obchodního cestujícího.
Je zadána množina nějakých bodů a pro každé dva z nich je zadána jejich vzdálenost. Uvažujeme cesty, které vychází z některého z daných bodů, projdou všemi body a vrátí se do výchozího.
Optimalizační verze: Najděte trasu nekratší délky. Převedeno na rozhodovací úlohu: Je dáno navíc číslo K. Rozhodněte, zda existuje trasa délky ≤ K. Obchodní cestující není zatím ve třídě P, ale je ve třídě NP úloh. NP úloha je taková úloha, kdy platí : pro každou „ano“ instanci lze v polynomiálním čase ověřit správnost odpovědi „ano“. Pro „ne“ instanci takový algoritmus neexistuje.
Třída NP je třída všech rozhodovacích úloh U, pro něž existuje nedeterministický algoritmus, pracující v polynomiálním čase. Nedeterministický algoritmus má dvě fáze. Nedeterministická, kdy se náhodně vygeneruje řetězec symbolů s a deterministická, kdy na vstupu úlohy je jak instance úlohy, tak řetězec s. Po konečném počtu kroků je výstupem „ano“ nebo „ne“. Řetězec s je vlastně navržené řešení úlohy, které se v deterministické části otestuje, zda platí. Pro obchodního cestujícího je to číslo K.
Redukce a polynomiální redukce
Obtížnost rozhodovacích úloh se dá srovnávat. Pojem „U se redukuje na V“ vlastně znamená, že rozhodovací úloha U není těžší než rozhodovací úloha V. U se redukuje na V, jestliže existuje algoritmus A, který pro každou instanci I úlohy U zkonstruuje instanci A(I) úlohy V tak, že I je „ano“ instance U právě když A(I) je „ano“ instance V. Je-li algoritmus A polynomiální, pak jde o polynomiální redukci.
NP úplné úlohy
Rozhodovací úloha U je NP úplná, jestliže je NP úloha a každá NP úloha se na U polynomiálně redukuje. Třídu NP úplných úloh označujeme jako NPC. (NP úplné úlohy jsou nejtěžší mezi NP úlohami). Není známo, zda třídy P a NP jsou opravdu různé. Jinak řečeno, o žádné úloze v NP se nepodařilo dokázat, že není v P. Podařilo se však nalézt úlohy, které jsou úplné ve třídě NP.
Příklady
Otázka (obtížné problémy):
Existuje pro každý problém efektivní (polynomiální) algoritmus, který ho řeší?
Odpověď:
Ne, existují problémy, pro které se dá dokázat, že neexistuje žádný efektivní algoritmus, který by daný problém řešil. Dokonce existují problémy, pro které se dá dokázat, že neexistuje žádný (ani neefektivní) algoritmus, který by daný problém řešil.
Námitka (neexistence algoritmů):
Jak dokázat, že něco neexistuje?
Odpověď:
Sporem. Předpokládáme, že to existuje a ukážeme, že z toho vyplývá nějaký závěr, který je ve zjevném rozporu se skutečností (typicky ukážeme, že něco musí být současně pravda i nepravda).
Příklad obtížného problému
Vstup: Uzavřená aritmetická formule vytvořená ze symbolů +, =, ∧, ∨, ¬, ∀, ∃, (, ), proměnných a celočíselných konstant.
Otázka: Je tato formule pravdivá v oboru přirozených čísel?
Příklad vstupu:
∀x∃y∀z((x + y = z) ∧ (y + 5 = x))
Pro tento problém je znám algoritmus se složitostí 22^2^O(n). Současně bylo dokázáno, že jakýkoliv algoritmus rešící tento problém má složitost minimálně 22^cn.
Příklad algoritmicky neřešitelného problému
Vstup: Uzavřená aritmetická formule vytvořená ze symbolů +, ×, =, ∧, ∨, ¬, ∀, ∃, (, ), proměnných a celočíselných konstant.
Otázka: Je tato formule pravdivá v oboru přirozených čísel?
Příklad vstupu:
∀x∃y∀z((x × y = z) ∧ (y + 5 = x))
Tento problém je algoritmicky neřešitelný (u rozhodovacích problémů se používá též pojem algoritmicky nerozhodnutelný). Úzce souvisí s Gödelovou větou o neúplnosti.
Další příklad nerozhodnutelného problému
Vstup: Počítačový program a nějaká jeho vstupní data.
Otázka: Zastaví se někdy tento program, když dostane na vstup tato data?
Idea důkazu nerozhodnutelnosti: Předpokládejme existenci programu H, který řeší tento problém. Můžeme ho snadno upravit na podprogram H′(p,v), který vrací „Ano" nebo „Ne" jako návratovou hodnotu. Vytvoříme nový program D: Vezme svůj vstup x a zavolá H′ jako H′(x,x).
Pokud H′ vrátí „Ano", D skočí do nekonečné smyčky.
Pokud H′ vrátí „Ne", D se zastaví.
Zastaví se program D nebo ne, když mu předložíme jako vstup jeho vlastní kód?
