Pamatujete si, co je NP-úplný problém? Čím se liší od prostého NP?

NP (nedeterministický polynomiální čas) — je třída problémů, u nichž lze řešení ověřit v polynomiálním čase. To znamená, pokud máte kandidáta na odpověď, můžete rychle zkontrolovat, zda je správná nebo ne.

NP-těžké problémy jsou podmnožinou NP, které jsou zároveň nej"obtížnější" v této třídě. Pokud by někdo našel polynomiální algoritmus řešení jakéhokoliv NP-těžkého problému, všechny problémy z NP by šlo řešit v polynomiálním čase.

Hlavní rozdíl:

• NP — problémy, jejichž řešení lze rychle ověřit.
• NP-těžké — problémy v NP, na které lze redukovat jakýkoliv jiný problém z NP (tedy jsou "nejkomplexnější" v NP).

Příklad: problém maximálního kliku v grafu je NP-těžký, a problém ověření, zda podmnožina prvků má součet roven zadanému číslu, je v NP.