Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2003/04

• Luogo delle lezioni: Aula 509
• Orario settimanale: Lun 15.00-18.00, Gio 16.00-18.00

Registro delle Lezioni

1. 16/10/03 (2h). introduzione: differenza tra problemi e algoritmi; algoritmi e modelli di calcolo; classi di problemi "indipendenti" dal modello di calcolo; problemi decidibili e semi-decidibili (relazione con logica matematica); classi naturali di complessita' ("problemi trattabili"). Prima formalizzazione: problemi di input/output e automi (deterministici) con stato, relazione di transizione, computazione, funzione calcolata. Esempio: problema della reachability (formulazione finitaria), algoritmo enumerativo esponenziale, algoritmo di visita polinomiale.
2. 20/10/03 (3h). Correttezza parziale e totale. Tecniche per dimostrare correttezza parziale e terminazione di un automa con stato, esempi di invariante e simulazione. Simulazione tra automi e sue proprieta'. Il modello di calcolo delle TM (ad un nastro) e automa associato. Linguaggio T-decidibile e T-semidecidibile. Le classi di linguaggi R e RE, inclusione di R in RE. Esempi informali di linguaggi appartenenti e non a R ed RE.

   23/10/03. indisponibilita' del docente.

   27/10/03. indisponibilita' del docente.

3. 30/10/03 (2h). La tesi di Church (invarianza di R ed RE al variare del modello di calcolo). Altri modelli di calcolo: TM a m-nastri (e dopo RAM). Varianti delle TM: input read-only, output write-only, traduttori. Le classi di complessita' tempo TIME_m(f) e TIME(f). La classe P dei problemi trattabili. La tesi di Church estesa (invarianza di P al variare del modello di calcolo). Inclusione di TIME_m(f) in TIME_1(O(f^2)) e simulazione di una TM a m-nastri con una TM ad 1 nastro. Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM offline. Inclusione di SPACE_m(f) in SPACE_1(O(f)) e simulazione di una TM a m-nastri di lavoro con una TM ad 1 nastro lavoro.
4. 03/11/03 (3h). Giustificazione della O-notazione: il teorema di tape-compression (rappresentazione di m caratteri con 1 carattere); Il teorema di linear speed-up (simulazione di molti passi con pochi passi). Il modello di calcolo delle RAM e automa associato. Confronto con il modello delle TM. Simulazione di una TM mediante RAM in O(f). Simulazione di una RAM mediante una TM con la tecnica del log file.
5. 07/11/03 (2h). Crescita lineare della dimensione degli interi e degli indirizzi di memoria modificati, simulazione di una RAM che lavora in tempo f con una TM che lavora in tempo O(f^3(n)). Impossibilita' di simulare una RAM con moltiplicazione che lavora in tempo polinomiale con una TM che lavora in tempo polinomiale.
6. 10/11/03 (3h). Le TM non-deterministiche (NDTM), definizione di linguaggio accettato/deciso e tempo/spazio di lavoro. Le classi di complessita' non-deterministiche NTIME(f) e NSPACE(f). Simulazione di una TM non-deterministica mediante una TM deterministica mediante visita BFS dell'albero delle possibili computazioni, e relazione tra NTIME e TIME/SPACE. Esempi di algoritmi non-deterministici per SAT e Reachability. Risultati di riduzione ad un nastro, speed-up e tape compression per le classi non-deterministiche. Relazione tra complessita' spazio e numero di configurazioni raggiungibili (tecnica di loop detection tramite contatore), e relazione tra SPACE e TIME. Classi di complessita' tempo-spazio e deterministiche e non: risultati di inclusione ovvi.
7. 13/11/03 (2h). Inclusione NSPACE in TIME e in SPACE (teorema di Savitch): ricerca di un cammino nel grafo delle ID di dimensione prefissata (con nodo target ausiliario). Sommario delle relazioni di inclusione tra classi di complessita'. Classi naturali e relazioni di derivate inclusione. La nozione di riduzione tra problemi. Proprieta' della riduzione, proprieta' di chiusura per riduzione dei problemi (semi)decidibili. Classi di linguaggi chiusi per riduzione e linguaggi C-completi. Riduzione poly-time.
8. 17/11/03 (3h). Proprieta' di chiusura delle classi naturali rispetto riduzione. Problemi banalmente C-completi per <, <_P Uso della riduzione per dimostrare la non (semi)decidibilita'. TM canoniche ed equivalenza tra TM e TM canoniche. Codifica TM canoniche come stringhe. La funzione universale U (per riconoscitori, traduttori, e U_m per m input). La TM universale M_U. Relazione tra la complessita' di M_U(< M >,x) e M(x). Varianti della TM universale per traduttori (con input read-only e output write-only), e per NDTM. I linguaggi H (halting problem, codifica delle coppie) e K, semidecidibilita' di H (usando la TM universale) e K (riducibile ad H). Non decidibilita' di K (e H). RE-completezza di H per < e <_P. Teorema S-m-n e definizione implicita di codifiche di TM.
9. 20/11/03 (2h). Esempi di proprieta' estensionali dei programmi. Non decidibilita' delle proprieta' estensionali dei programmi (Teorema di Rice). Proprieta' di chiusura di R ed RE rispetto ai connettivi logici. Caratterizzazione di R in termini di RE (RE non e' chiuso per complementazione). Predicato di Kleene (codifica di computazioni come sequenze di quintuple). Caratterizzazione di RE in termini di R (predicato di Kleene). Proprieta' di chiusura di R per quantificazione limitata. Chiusura di RE per quantificazione esistenziale illimitata, e per quantificazione limitata.
10. 24/11/03 (3h). R e RE non sono chiusi per quantificazione universale illimitata. Caratterizzazione di R ed RE in termini di enumerazioni. Teoremi di gerarchia spazio e tempo. Inclusioni strette tra classi naturali di complessita'. Inesistenza di linguaggi R_completi per <_P. Riduzione log-space <_L, proprieta' transitiva di <_L e tecnica demand-driven.
11. 25/11/03 (2h). ESERCIZI su calcolabilita' del tipo "dire se un linguaggio appartiene ad R o RE". TOT ed EQ non sono in RE. Dimostrazione per assurdo che funzioni con certe proprieta' non sono calcolabili.
12. 27/11/03 (2h). Proprieta' di chiusura delle classi naturali rispetto ad operazioni insiemistiche, e quantificazione limitata (per L e NL si usa tecnica demand-driven). Problemi completi rispetto a <_L: varianti della TM universale, e problemi completi per NL, P, NP e PSPACE ottenuti da varianti dell'halting problem.
13. 01/12/03 (3h). Caratterizzazione di NP in termini di P (sfruttando analisi di complessita' per la TM universale e per il predicato di Kleene). Esempi di problemi RE-completi di natura logica: {(Ax,eq) | eq e' derivabile da Ax nella logica equazionale}, {F| F tautologia della logica del primo ordine}. Problemi logici che risultano essere completi per qualche classe naturale: CVP (P), SAT (NP), k-SAT (NP se k>2), 2-SAT (NL), HORNSAT (P), QBF (PSPACE). Metodo della tabella: corrispondenza riga descrizione istantanea, corrispondenza tabella computazione. P-completezza di CVP: Codifica booleana di una tabella, Circuito buoleano per calcolare la tabella corrispondente ad una computazione. NP-completezza di SAT: codifica di una tabella mediante variabili booleane; formula in CNF per esprimere che esiste una tabella che rappresenta una computazione accettante.
14. 02/12/03 (2h). NP-completezza di (riduzione di SAT a) 3-SAT. P-completezza di (riduzione di CVP a) MONOTONE CVP. HORNSAT P-completo: costruzione del modello minimo e verifica dei goal; riduzione di CVP a HORSAT (simile a riduzione a monotone CVP). Reachability e' NL-completo: mappare x in un problema di reachability per il grafo delle ID di M con input x, con M NDTM con input read-only che lavora in spazio logaritmico. QBF PSPACE-completo (formula compatta, ma non in CNF, per esprimere P(u,v,n) esiste un cammino di lunghezza <= 2^n da u a v nel grafo delle ID di M con input x).
15. 04/12/03 (2h). Problemi NP-completi su grafi non-orientati: 3_SAT < independent set < node cover, clique; 3-colorability (senza dimostrazione). Problemi NP-completi su grafi orientati: hamilton path, travelling salesman problem. Problemi NP-completi numerici: integer programming (ma linear programming e' in P). Accenni ad algoritmi randomizzati e riduzione della probabilita' di errore mediante ripetizione: test A*B=C in tempo O(n^2). Accenni ad algoritmi paralleli: calcolo di A*B in tempo O(log n).

    08/12/03 (VACANZA)

16. 09/12/03 (2h). Chiusura per concatenazione di NP e P (usare quantificazione log-limitata). Chiusura per Kleene star di NP (usare quantificazione poly-limitata) e P (usare programmazione dinamica). Chiusura per coding di NP. P non e' chiuso per coding, se P non coincide con NP. NP e' diverso da SPACE(n) (quest'ultimo non e' chiuso per riduzione log-space). Esercizi su COMPLESSITA'.

    11/12/03 docente assente.

    15/12/03 sospensione lezioni causa sciopero.

17. 18/12/03 (2h). ESERCIZI d' esame.