Ricorda cos'è un problema NP-completo? In cosa si differenzia da semplicemente NP?

NP (tempo polinomiale non deterministico) è una classe di problemi per i quali la soluzione può essere verificata in tempo polinomiale. Ovvero, se hai un candidato alla risposta, puoi verificarne rapidamente la correttezza o meno.

I problemi NP-completi sono un sottoinsieme di NP che sono allo stesso tempo i più "difficili" in questa classe. Se qualcuno trovasse un algoritmo polinomiale per risolvere qualsiasi problema NP-completo, allora tutti i problemi in NP potrebbero essere risolti in tempo polinomiale.

Differenza principale:

• NP: problemi le cui soluzioni possono essere verificate rapidamente.
• NP-completi: problemi in NP a cui si può ridurre qualsiasi altro problema NP (cioè, sono i "più difficili" in NP).

Esempio: il problema del massimo clique in un grafo è NP-completo, e il problema di verificare se un sottoinsieme di elementi somma a un numero dato è in NP.