Pamätáte si, čo je NP-úplný problém? Čím sa líši od jednoduchého NP?

NP (nedeterministický polynomiálny čas) — je trieda problémov, pre ktorých je možné riešenie overiť v polynomiálnom čase. To znamená, ak máte kandidáta na odpoveď, môžete rýchlo skontrolovať, či je správny alebo nie.

NP-ťažké problémy sú podmnožinou NP, ktoré sú súčasne naj"zložitejšie" v tejto triede. Ak by niekto našiel polynomiálny algoritmus na riešenie akéhokoľvek NP-ťažkého problému, všetky problémy z NP by sa dali riešiť v polynomiálnom čase.

Hlavný rozdiel:

• NP — problémy, ktorých riešenia je možné rýchlo overiť.
• NP-ťažké — problémy v NP, na ktoré sa dá zredukovať akýkoľvek iný problém z NP (teda sú "najzložitejšie" v NP).

Príklad: problém maximálneho kliku v grafe je NP-ťažký, a problém overenia, či podmnožina prvkov má súčet rovný zadanému číslu, je v NP.