První rozdělení všech problémů jsme již učinili a to na takové, které jsou algoritmicky řešitelné a algoritmicky neřešitelné. Další klasifikace vychází z horního omezení času výpočtu pro velikost vstupu n. Většina našich algoritmů pro řešení problémů, které jsme zkoumali, měla v nejhorším případě čas výpočtu O(nk) pro nějakou konstantu k, tj. polynomiální. Na druhé straně jsou řešitelné problémy, o nichž víme, že nemají algoritmus s polynomiálním časem výpočtu. Příkladem je problém Hanojských věží, kde minimální počet přesunů disků je 2n - 1.
Problémy, které jsou řešitelné v polynomiálním čase považujeme za zvládnutelné, neboli lehké a problémy, které vyžadují superpolynomiální čas považujeme za nezvládnutelné, neboli těžké.
Podobně jako při zkoumání řešitelnosti problémů, omezíme se na rozhodovací problémy. Na druhé straně mnoho prakticky důležitých problémů jsou optimalizační problémy, kdy výstupem je hodnota, která nejlépe splňuje zadaná kritéria. Příkladem může být problém, který nazveme NEJKRATŠÍ-CESTA. V grafu G je úkolem najít mezi jeho vrcholy u a v cestu s nejmenším počtem hran. Obvykle můžeme optimalizační problém převést na problém rozhodovací. Pro uvedený problém NEJKRATŠÍ-CESTA odpovídající problém, který nazveme CESTA, je problém jestli v daném grafu G existuje mezi vrcholy u a v cesta mající délku nejvíce k hran. Známe-li řešení optimalizačního problému, víme najít řešení rozhodovacího problému. Vyřešením problému NEJKRATŠÍ-CESTA a porovnáním nalezené hodnoty s k získáme řešení problému CESTA.
Můžeme tedy říct, že rozhodovací problém je „lehčí“ nebo alespoň není „těžší“ než problém optimalizační. Ukážeme-li, že rozhodovací problém je těžký, ukážeme, že i optimalizační problém je těžký.
Pro řešení abstraktního problému na počítači jeho instance (vstupy) musí být kódovány do binárních řetězců. Když počítač řeší nějaký abstraktní problém, ve skutečnosti řeší jeho zakódovanou instanci. Problém v tomto tvaru nazýváme konkrétní.
Konkrétní problém je řešitelný v polynomiálním čase, existuje-li algoritmus, který ho řeší v čase O(nk).
Třída složitosti P je množina všech konkrétních problémů řešitelných v polynomiálním čase.
Vztah k časové náročnosti řešení abstraktního problému však není přímočarý, ale značně závisí na kódování.
Uveďme jako příklad zjištění hrany mezi dvěma vrcholy grafu. Je-li graf zakódován maticí sousednosti je čas výpočtu Θ(1) a je-li zakódován seznamy sousednosti je Θ(n), kde n = │V│.
Podobně mějme algoritmus, kterého vstup je celé číslo k a časová náročnost je Θ(k). Velikost vstupu takových algoritmů vyjadřujeme počtem znaků pro jeho reprezentaci. V unární reprezentaci (Římané ji použili pro k=1,2,3) to bude řetězec k jedniček a pro vstup velikosti n je k = n a algoritmus je v čase polynomiální - Θ(n). Použijeme-li obvyklé kódování v dvojkové soustavě, pro číslo k délka vstupu bude n ≈ log2k. V tomto případě čas výpočtu bude Θ(2n), tedy exponenciální.
Dále budeme uvažovat standardní kódovaní, tj. čísla v dvojkové soustavě a znaky v ASCII kódu (Unicode) a nebudeme rozlišovat mezi abstraktními a konkrétními problémy.
Pro některé rozhodovací problémy neumíme nalézt řešení v polynomiálním čase, ale na druhé straně pro ně existuje polynomiální verifikační algoritmus. Verifikační algoritmus ověří řešení problému na základě poskytnutých dat, která nazveme certifikát.
V článku 2.3 jsme se setkali s problémem splnitelnosti booleovských formulí, kde navrhnuté řešení pro n proměnných prověřovalo 2n možností. Pokud nám někdo řekne, že daná booleovská formule je splnitelná a nabídne nám hodnoty jednotlivých proměnných pro ověření svého tvrzení, můžeme dosazením těchto hodnot a vyhodnocením booleovské formule verifikovat zda tomu tak je, jistě v polynomiálním čase.
Dostáváme tak schéma:
Problém: Je zadaná booleovská formule splnitelná?
Zadaná formule: P V Q V R
Certifikát: P = true, Q = false, R = false
Verifikační algoritmus: Vyhodnocení formule pro zadaný certifikát
Podobně pro následující problém.
Problém: Je v zadané množině celých čísel podmnožina, která má součet
prvků rovný nule?
Zadaná množina: { -7, -2, -3, 5, 6 }
Certifikát: { -2, -3, 5 }
Verifikační algoritmus: Kontrola jsou-li prvky certifikátu prvkami
množiny a jejich sčítání
Vlastnosti verifikačního algoritmu si vysvětlíme na problému splnitelnosti booleovských formulí. Má dva vstupy, formuli, tj. instanci problému, a certifikát. Pro každou splnitelnou formuli existuje certifikát, pro který algoritmus ověří, že formule je splnitelná. Není-li booleovská formule splnitelná, neexistuje certifikát, na kterého základě by algoritmus formuli ověřil jako splnitelnou.
Tyto vlastnosti jsou pro verifikační algoritmy obecné a má je i verifikační algoritmus pro problém má-li množina celých čísel podmnožinu, která má součet prvků rovný nule.
Problémy, pro které existuje polynomiální verifikační algoritmus, tvoří třídu složitosti NP - nedeterministicky polynomiální.
Polynomiálnost verifikačního algoritmu vyžaduje, aby certifikát měl polynomiální velikost v závislosti na velikosti instance problému, protože polynomiální počet instrukcí může přistoupit jen k polynomiálnímu počtu paměťových míst.
Položme si otázku jaký je vztah třídy P a třídy NP? Je-li nějaký problém ve třídě P, potom verifikační algoritmus sestrojíme tak, že ignoruje vstup, který je certifikátem a ze vstupů, které jsou instancemi problémů ověří ty, pro které nalezne řešení existující polynomiální algoritmus. Příkladem je zmíněný problém CESTA, pro který jsem uvedli algoritmus, který pro zadanou instanci problému v polynomiálním čase rozhodne, zda v grafu G mezi vrcholy u a v existuje cesta s délkou nejvíce k hran, protože jak víme z článku 6.2 nalezení (některé) nejkratší cesty je O(n). Vidíme, že jsme nemuseli zadat žádný certifikát, kterým by byla některá z nejkratších cest.
Je tedy P Í NP. Třída P obsahuje problémy, pro které umíme najít řešení rychle. Třída NP obsahuje problémy, kterých řešení umíme ověřit rychle. Není známo jestli je P = NP. Většinou se soudí, že P ≠ NP. K této domněnce přispívá existence NP-úplných problémů, kterými se budeme zabývat v kapitole 12.