Třídy problémů
Některé problémy jsou těžší než jiné. Při posuzování obtížnosti problémů se ukázalo jako užitečné rozdělit problémy do tříd složitosti, které značíme:
PTIME - problémy řešitelné v polynomiálním čase
PSPACE - problémy řešitelné s polynomiálním množstvím paměti
EXPTIME - problémy řešitelné v exponenciálním čase
EXPSPACE - problémy řešitelné s exponenciálním množstvím paměti
Třída NPTIME
Jednou z nejdůležitějších tříd je třída NPTIME. Do třídy NPTIME patří rozhodovací problémy, pro které existuje polynomiální algoritmus, který ověří správnost nalezeného řešení. Přesněji řečeno, pokud je odpověď „Ano", existuje svědek, který dosvědčuje, že odpověď je „Ano", kterého je možné v polynomiálním čase otestovat, že tomu tak skutečně je. Pokud je odpověď „Ne", žádný takový svědek neexistuje.
Příklad problému z NPTIME
Vstup: Popis mapy (seznam států a informace který stát sousedí s kterým) a číslo k.
Otázka: Je možné státy obarvit k barvami tak, aby žádné dva sousední státy neměly stejnou barvu?
P vs. NP
Jeden z největších otevřených problémů teoretické informatiky:
Otevřený problém: Je P = NP?
Pozn.: Třídy PTIME a NPTIME bývají také označovány stručněji P a NP.
NP-úplné problémy
Důležitou podtřídou třídy NPTIME jsou tzv. NP-úplné problémy.
Definice Problém P je NP-těžký, jestliže platí, že libovolný problém ze třídy NPTIME je možné v polynomiálním čase redukovat na problém P.
Definice Problém P je NP-úplný, jestliže je NP-těžký a současně sám patří do třídy NPTIME.
NP-úplné problémy jsou důležité, protože:
- Kdyby alespoň jeden z nich byl řešitelný v polynomiálním čase, všechny problémy z NPTIME by byly řešitelné v polynomiálním čase.
- Pokud v NPTIME existuje alespoň jeden problém, který není řešitelný v polynomiálním čase, pak žádný z NP-úplných problémů není řešitelný v polynomiálním čase.
- Velké množství problémů, které se objevují v praxi v různých oblastech informatiky, je NP-úplných nebo NP-těžkých.
- To, že NP-úplné problémy nelze řešit v polynomiálním čase je podmínkou nutnou (nikoli však postačující) pro to, aby existovaly šifrovací algoritmy, které by nebyly snadno prolomitelné.
Někdy dva problémy mohou vypadat podobně, a přitom jeden z nich je řešitelný v polynomiálním čase, zatímco druhý je NP-úplný.
Problém 1
Vstup: Popis měst a silnic.
Výstup: Existuje okružní cesta, na které projedeme každou silnici právě jednou?
Problém 2
Vstup: Popis měst a silnic.
Výstup: Existuje okružní cesta, na které projedeme každé město právě jednou?
Problém 1 je v PTIME.
Problém 2 je NP-úplný.
Jak řešit těžké problémy?
Pokud pro daný problém neexistuje efektivní algoritmus, máme následující možnosti:
- Exponenciální algoritmy – použitelné jen na malé instance.
- Aproximační řešení – použitelné jen pro optimalizační problémy. Najde řešení, které je o něco horší než optimum.
- Pravděpodobnostní (randomizované) algoritmy – najde rychle řešení, ale řešení je s určitou pravděpodobností špatně.
- Speciální případy – soutředit se jen na některé speciální případy instancí, neřešit problém v plné obecnosti.
- Heuristiky – postup, který najde řešení rychle ve většině „rozumných" případů, není však zaručeno že vždy.
Příklad: Randomizovaný algoritmus
Zadání:
Vstup: Přirozené číslo p.
Otázka: Je p prvočíslo?
Teprve od roku 2003 je znám polynomiální algoritmus (O(n12+ε), později o něco zlepšen). V praxi je používán randomizovaný algoritmus se složitostí O(n3):
Pokud p je prvočíslo, vrátí vždy odpověď „Ano". Pokud p není prvočíslo, je pravděpodobnost odpovědi „Ne" minimálně 50%, ale existuje až 50% šance, že program vrátí chybnou odpověď „Ano".
Program můžeme volat opakovaně (k krát). Pokud program vrátí alespoň jednou odpověď „Ne", víme na 100%, že p není prvočíslo. Pokud program vrátí pokaždé „Ano", je pravděpodobnost toho, že p není prvočíslo, menší než 2−k. Když k = 100, je pravděpodobnost chyby zanedbatelně malá.
Poznámka: Lze například odvodit, že pravděpodobnost toho, že počítač bude zasažen během dané mikrosekundy meteoritem, je nejméně 2−100 za předpokladu, že každých 1000 let je meteoritem zničeno alespoň 100 m2 zemského povrchu.
