Calcolabilità e Complessità Computazionale
Macchine di Turing, P vs NP, indecidibilità, classi di complessità, riduzioni. Da 1.155 file teoria classificati (corso magistrale).
📚 Prerequisiti
- Matematica discreta
- Algoritmi
🎯 Cosa imparerai
- Comprendere i limiti del calcolabile
- Dimostrare indecidibilità via riduzione
- Classificare problemi in P/NP/PSPACE
- Riconoscere problemi NP-completi nella pratica