Sintesi delle lezioni

• 2 Ottobre
  • Presentazione del corso.
  • 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