Îți amintești ce este o problemă NP-completă? Cu ce diferă de simpla NP?

NP (timp polinomial nedeterminist) — este o clasă de probleme pentru care soluția poate fi verificată în timp polinomial. Adică, dacă ai un candidat pentru răspuns, poți verifica rapid dacă este corect sau nu.

Problemele NP-complete sunt un subset al NP care sunt în același timp cele mai "dificile" din această clasă. Dacă cineva ar găsi un algoritm polinomial pentru rezolvarea oricărui problemă NP-completă, atunci toate problemele din NP ar putea fi rezolvate în timp polinomial.

Diferența principală:

• NP — probleme ale căror soluții pot fi verificate rapid.
• NP-complete — probleme din NP la care se poate reduce orice altă problemă NP (adică, sunt cele "mai dificile" din NP).

Exemplu: problema maximului de clique într-un graf este NP-completă, iar problema verificării dacă un subset de elemente are suma egală cu un număr dat este în NP.