- Problemi Decidibili
- Trattabili (complessità polinomiale)
- Intrattabili (complessità esponenziale)
- Problemi Indecidibili
- Problemi decisionali (sì/no)
- Ottimizzazioni (il migliore è n)
ma a ogni problema di ottimizzazione può essere associato un problema decisionale
- Classe P: problemi risolvibili in tempo polinomiale O(nk)
- Classe NP: problemi verificabili in tempo polinomiale O(nk)
P ⊆ NP
NPC???