Skip to content

6.3 Třídy složitosti P a NP

6.3 Třídy složitosti P a NP

Definice (Typy problémů)

Typy problémů

  • Rozhodovací problém: Problém, na který lze odpovědět pouze ANO či NE.
    • Příklad: „Lze graf obarvit 3 barvami?“
    • Problém lze chápat jako jazyk \(L_{ano}\) obsahující všechny instance, kde je odpověď ANO.
  • Optimalizační problém: Problém, který hledá optimální řešení (minimum/maximum).
    • Příklad: „Kolik nejméně barev je třeba k obarvení grafu?“

Poznámka: Optimalizační a rozhodovací verze téhož problému jsou obvykle výpočetně stejně náročné.

Definice (Rozhodnutelnost)

Rozhodnutelnost

  • Rozhodnutelné problémy: Existuje algoritmus (Turingův stroj), který problém vyřeší (vždy se zastaví). Odpovídají rekurzivním jazykům.
  • Nerozhodnutelné problémy: Nejsou rozhodnutelné (neexistuje algoritmus, který by pro libovolný vstup vždy skončil a dal správnou odpověď). Odpovídají nerekurzivním jazykům.
    • Příklad: Problém zastavení (\(L_{HALT}\)).

Definice (Třída P)

Třída P

Třída P je třída rozhodovacích problémů, které lze řešit v polynomiálně omezeném čase na deterministickém Turingově stroji.

Definice (Třída NP)

Třída NP

Třída NP je třída rozhodovacích problémů, které lze řešit v polynomiálně omezeném čase na nedeterministickém Turingově stroji.

Vztah P a NP

Platí \(P \subseteq NP\). Zdali \(P = NP\) je stále otevřený problém. Obecně se však věří, že třída P je vlastní podmnožinou třídy NP (tedy \(P \subsetneq NP\)).

Definice (NP-těžký a NP-úplný problém)

NP-těžký a NP-úplný problém

  • NP-těžký (NP-hard) problém: Problém, na který lze v polynomiálním čase převést (redukovat) všechny ostatní problémy ze třídy NP. Sám však v NP být nemusí.

    NP hard NP hard

  • NP-úplný (NP-complete) problém: Problém, který je NP-těžký a zároveň sám patří do třídy NP. Jsou to „nejtěžší“ problémy v NP.

    NP complete NP complete

Příklady: Problém obchodního cestujícího, SAT.

Definice (Polynomiální redukce)

Polynomiální redukce

Mějme dva rozhodovací problémy \(A\) a \(B\). Řekneme, že \(A\) se polynomiálně redukuje na \(B\) (značíme \(A \le_p B\)), pokud existuje funkce \(f\) vypočitatelná v polynomiálním čase, která převede každou instanci problému \(A\) na ekvivalentní instanci problému \(B\).

Tedy: Odpověď pro instanci \(I_A\) je ANO \(\iff\) odpověď pro \(f(I_A)\) je ANO.

Polynomiální redukce Polynomiální redukce

K čemu slouží redukce?

Pokud platí \(A \le_p B\):

  • Problém \(B\) je alespoň tak těžký jako \(A\).
  • Pokud bychom uměli efektivně (v P) vyřešit \(B\), uměli bychom efektivně vyřešit i \(A\).
  • Pokud \(A\) není v P (je těžký), pak ani \(B\) nemůže být v P.