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.
- 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
This topic: Complessita
> WebHome > Diariolezioni
Topic revision: r10 - 2012-12-20 - AngeloMonti