Lezione del 11/12/2008

Problemi computazionalmente intrattabili. Le classi di problemi P e NP. Congettura P diverso da NP. Problemi NP-Completi. Teorema di Cook-Levin: NP-Completezza del problema della soddisfacibilita' (senza dimostrazione). Riduzioni polinomiali ed NP-Completezza. Il problema della 3-soddisfacibilita' e' NP-Completo: riduzione da soddisfacibilita'.