per qualsiasi errore, potete segnalarmelo su telegram @LuigiBrosNin o qui con un commento grazie per la collaborazione!

Teoria

da quel che vedo al momento, le slide del prof sono di ottima qualità 😄

Tesi di Church-Turing, macchina di Turing ed altri modelli di calcolo

La macchina universale, problemi indecidibili

Riduzioni tra problemi, teorema di rice, diagonalizzazione

Classi di complessità, classe P, riduzioni polinomiali

Classe NP, teorema di Cook Levin

Gerarchia di complessità, randomness

Indecidibilità della logica del prim’ordine e incompletezza (non richiesto all’esame)

Classe BPP, Interactive proof (non richiesto all’esame)

Esame

nota: le esercitazioni non c’entrano una fava con l’esame :)