Polynomialna trieda zlozitosti P
Obsahuje problemy, pre ktore existuje riesenie v polynomialne obmedzenom case. Algoritmus by mal mat rad rastu O(n^k).
Trieda zlozitosti NP
NP ulohy riesime tak, ze riesenie uhadneme a overime. Efektivny algoritmus pre riesenie tychto uloh nie je znamy, hoci nie je mozne vylucit, ze neexistuje. Pre overenie uhadnuteho vysledku vsak existuje P algoritmus
Algoritmu, ktory je nedeterministicky ma nedeterministicku fazu a deterministicku fazu. V tej prvej sa do pamate zapise nejake uhadnute riesenie a v tej druhej, deterministickej sa P algoritmom overi riesenie.
Prikladom je najst sucet cisel, ktory je rovny 0, v zadanej mnozine cisel. Jednoduchy priklad pre malu mnozinu cisel, ale prilis zlozity pre velku mnozinu. Ak by sme ale vybrali nejaku podmnozinu, tak je lahke overit, ci plati, alebo nie.
Prikladmi takychto uloh je
- plnenie krabic
- sucet podmnoziny
- problem batohu
- zafarbenie grafu
- Hammiltonovske kruznice v grafe
NP-uplne problemy
To su take problemy, na ktore su redukovatelne vsetky ostatne problemy z NP. Redukovatelne znamena, ze ak mame problem A a B, tak A je redukovatelne na B, ak je B riesenim aj A NP-uplne ulohy su tie najtazsie ulohy - napriklad problem obchodneho cestujuceho.
