argomenti tipici di un corso di calcolabilità e argomenti tipici di un corso di complessità.
numeri transfiniti, cardinalità dei reali, ipotesi del continuo
metodo della diagonalizzazione di Cantor, esistenza di funzioni non calcolabili.
problemi decidibili e problemi semidecidibili.
ultimo teorema di Fermat, la congettura di Colatz, la congettura di Goldbach
5 Ottobre
indecidibilità del problema della fermata.
prove di indecidibilità tramite la tecnica della riduzione: indecidibilità del problema dell'equivalenza e del problema della corrispondenza di Post
Tesi di Church-Turing.
Tesi del calcolo sequenziale.
9 Ottobre
macchine di Turing a uno o più nastri
algoritmi per il riconoscimento di palindromi e lower bound Omega(n^2) nel caso di macchine ad un solo nastro.
12 Ottobre
problemi trattabili e problemi intrattabili, la classe P
la gerarchia esponenziale di tempo, e la classe ELEMENTARY
le gerarchia esponenziale di spazio
relazione tra le classi delle due gerarchie: P \subseteq PSPACE \subseteq EXPTIME \subseteq EXPSPACE .....
15 Ottobre
il problema della fermata limitata, un risultato di separazione: P \subset EXPTIME
padding argument: se P= PSPACE allora EXPTIME=EXPSPACE
19 Ottobre
dentro la classe P. Il modello di calcolo per classi sublineari.
se un problema risolvibile in spazio s(n) = \omega (log n) allora risolvibile in tempo 2^O(s(n)).
la gerarchia L\subset 2L \subset 3L ..... e L\subseteq P
il problema della s,t-connettività. Sua appartenenza alla classe P e alla classe 2L
classi di complessità probabilistiche.
23 Ottobre
variabili casuali, valore atteso e diseguaglianza di Markov
la classe RL
passeggiate casuali e s,t-connettività in RL
cover time e hitting time di grafi
cover time esponenziale per grafi diretti.
26 Ottobre
passeggiate casuali e il problema della soddisfacibilità
algoritmo probabilistico per 2SAT in tempo O(n^4)
30 Ottobre
algoritmo probabilistico per 3SAT in tempo O(n^5(4/3)^n)
riduzioni tra problemi e completezza.
2 Novembre giorno di festa
6 Novembre
i verificatori e la classe NP, i confutatori e la classe co-NP
P \subseteq NP \subseteq PSPACE
il teorema di Ladner e la classe NPI
i problemi NP completi e i problemi co-NP completi
le classi QP e SUBEXP e l' Exponential-Time Hypothesis (ETH)
il problema della fattorizzazione e il problema dell'isomorfismo tra grafi.
9 Novembre
Algoritmi randomizzati e algoritmi probabilistici.
algoritmi tipo Montecarlo e tipo Las Vegas
la classe PP e la classe BPP
il lemma di amplificazione
13 e 16 settimana degli esoneri
20 Novembre
le classi RP e co-RP
il problema di verificare se un polinomio e' identicamente nullo e il problema dell'uguaglianza di polinomi
il torema di Schwartz
23 Novembre
PP \subseteq PSPACE,
RP\subseteq NP e co-RP\subseteq co-NP
la classe ZPP
27 Novembre
un problema A appartiene alla classe ZPP se e solo se ha tempo atteso polinomiale
la classe #P, FP\subseteq #P, FP=#P se e solo se P=PP.
cook riduzioni e problemi #P completi, riduzioni polinomiali parsimoniose
il problema di contare i diversi alberi di copertura di un grafo. Teorema di Kirchhoff e la formula di Cayley.
30 Novembre
FESTA
4 Dicembre
il problema di contare il numero di cicli in un grafo. #ciclo è in FP implica NP=P
il problema di contare gli assegnamenti che soddisfano un certa formula booleana in DNF. #DNF è #P completo
7 Dicembre
il metodo di Monte Carlo per problemi di conteggio. La classe di complessità probabilistica FPRAS
il problema #DNF è in FPRAS (applicazione del metodo di Monte Carlo)
metodo della mediana per amplificare la probabilità di successo in un algoritmo di \epsilon-approssimazione
11 Dicembre
enunciato e prova del Chernoff bound.
Classi di complessità per problemi di ottimizzazione. Le classi NPO e PO.
problemi di ottimizzazione NP-ardui
PO=NPO se e solo se P=NP
14 Dicembre
rapporto d'approssimazione e algoritmi approssimanti per il problema della massima cricca (MAX CLIQUE) e il problema dela massima soddisfacibilità (MAXSAT)
le classi APX, PTAS e FPTAS
se P diverso da NP allora il problema del commesso viaggiatore è in NPO-APX
18 Dicembre
se P diverso da NP allora il problema del Bin Packing è in APX-PTAS
se P diverso da NP allora i problemi di ottimizzazione polinomialmente limitati con versione decisionale NP-comleta non possono avere uno schema di approssimazione completamente polinomiale.
se P diverso da NP allora il problema dello Zaino è in FPTAS-PO