Teoria degli Algoritmi e Calcolabilita’

Eugenio Moggi (stanza 229 tel. 353 6629)

C.L. in Scienze dell’Informazione, A.A. 1995-96

Premessa

Lo scopo del corso e’ di presentare le nozioni fondamentali ed i principali risultati di teoria della calcolabilita’, teoria della complessita’ e logica matematica. Inoltre si accennera’ ad alcuni sviluppi recenti in teoria della complessita’.

Prerequisiti

Si suppongono noti i contenuti dei corsi informatici del primo biennio e le nozioni di base fornite dai corsi matematici del primo biennio.

Contenuto

Il corso e’ articolato in due parti Complessita’ (con accenni di Calcolabilita’) e Logica (mutuata dal corso di Logica Matematica del Prof. Rosolini).

• Problemi ed algoritmi, macchine di Turing e random access machines (tesi di Church), calcolabilita’ (macchine universali, problemi indecidibili, riduzioni), classi di complessita’ (P, NP, PSPACE), riduzioni e completezza, problemi P-completi e NP-completi.

Panoramica su: algoritmi probabilistici e macchine di Turing probabilistiche (RP), problemi approssimabili, algoritmi paralleli e circuiti (NC).

Capitoli del libro di testo: 1, 2, 3 (escluso recursive inseparability), 7 (integrato con note su teoremi di gerarchia), 8 (escluso 8.3), 9; 11, 13, 15 (escluso 15.4).

• Logica proposizionale ed espressioni booleane, validita’ e soddisfacibilita’, logiche di Horn. Logica del primo ordine, modelli, teorema di deduzione, teorema di completezza, teorema di compattezza. Logica del secondo ordine. Teoria dei numeri, teorema di incompletezza di Gödel (cenni).

Capitoli del libro di testo: da precisare.

Testo consigliato. Il corso e’ basato sul libro

References

[Pap94] C.M. Papadimitriou, Computational Complexity. Addison-Wesley, 1994.

Tale libro e’ disponibile in biblioteca, e puo’ essere sostituito da altri libri che coprano gli argomenti trattati nei seguenti capitoli: 1-5, 7-9, 11, 13, 15.

Argomenti delle lezioni (Moggi)

• 08/11/95 (L 1-2) Panoramica degli argomenti del corso; esempi di problemi di decisione in P (trattabili), NP (intrattabili) e NC (parallelizzabili), algoritmi approssimati e probabilistici; enunciazione informale della tesi di Church (estesa).

Macchina di Turing M (inclusi dettagli “irrilevanti”), configurazione istantanea (finita ed infinita) ID_{M}, relazione di transizione →_{M}; nozioni derivate: M decide L, M accetta L, M calcola f.

O-notazione: O(f), Ω(f), θ(f). codifica di numeri, matrici e grafi; irragionevolezza della codifica unaria dei numeri. Analisi degli algoritmi e TM (problema, codifica e trattabilita’): palindrome.

• 10/11/95 (L 3) CH 2 Varianti della TM: a k nastri, input read-only, output write-only; M richiede tempo u con input x, classi di complessita’ tempo T IME_{k}(t) e T IME(t); M richiede tempo u con input x (varianti), classi di complessita’ spazio SP ACE(s) e SP ACE_{k}(s). palindrome in T IME(O(n)) e SP ACE(O(logn)).

• Lun 13/11/95 (L 4-5) T IME_{k}(f) ⊆ T IME_{1}(O(f^{2})) [Thm 2.1], tecnica della simulazione, T IME_{k}(f) ⊆ T IME_{2}(O(f log f))? [Ex 2.8.9], SP ACE_{k}(f) ⊆ SP ACE_{1}(f); T IME_{k}(f) ⊆ SP ACE_{k}(O(f)).

Speed-up [Thm 2.2] T IME(f) ⊆ T IME(g) se f ∈ O(g) e g(n)/n → ∞, simulare molti passi con pochi, trattare gli input di dimemsione ≤ n_{0} usando lo stato finito di una TM, la classe naturale P.

Tape-compression [Thm 2.3] SP ACE(f) ⊆ SP ACE(g) se f ∈ O(g), (al contrario dello speed-up) vale anche per macchine che calcolano funzioni.

• Mar 14/11/95 (L 6) Corroborazione della Tesi di Church (estesa): le funzioni calcolabili in tempo polinomiale usando TM e RAM coincidono.

Descrizione di una RAM: programma, istruzioni (read, store, load, add, sub, half, jump, halt), program counter, inputs, accumulatore e registri, indirizzi diretti ed indiretti. Semantica di un operando ed una istruzione, stato della RAM (k, R), relazione di transizione →_{Π,I}, funzione da sequenze di interi ad interi calcolata da una RAM.

Dimensione dell’input di una RAM e complessita’ tempo (istruzioni a costo unitario); il problema causato dalla moltiplicazione: x ↦ x^{x} e’ calcolabile in tempo polinomiale da una RAM con moltiplicazione (ma non da una TM), tuttavia la moltiplicazione e’ realizzabile in tempo polinomiale.

Lemma di upper-bound sul contenuto dei registri dopo t passi l(r) ≤ t+l(I)+l(Π) [non vale in presenza della moltiplicazione].

• Mer 15/11/95 (L 7-8) Simulazione di TM tramite RAM [Thm 2.4] L ∈ T IME(f) implies ϕ_{L} calcolata da una RAM in tempo O(f), codifica numerica di Σ, un registro per ogni casella della TM (accesso diretto alle caselle).

Simulazione di RAM tramite TM [Thm 2.5] ϕ calcolabile da una RAM in tempo f implica ϕ calcolabile da una TM in tempo O(f^{3}), codifica binaria di input e registri, nastro con il log delle modifiche ai registri [dimensione O(f^{2})] e determinazione del contenuto di un registro (backup incrementale).

Le TM non-deterministiche, M accetta L, M richiede tempo/spazio ≤ u con input x, (differenze ed analogie con DTM); classi di complessita’ non-deterministiche NT IME(f) e NSP ACE(f); risultati di base per le classi non-deterministiche, ottenuti riciclando le dimostrazione degli stessi risultati per le classi deterministiche, NT IME_{k}(f) ⊆ NT IME_{2}(O(f))? [Ex 2.8.17]; la classe NP, esempi TSP(D).

• Lun 20/11/95 (L 9-11) Relazioni tra classi deterministiche e non-deterministiche T IME(f) ⊆ NT IME(f) ⊆ SP ACE(f), ∪_{c>1}T IME(c^{f}) [Thm 2.6] ricerca esaustiva.

La classe NSP ACE(log), esempi reachability (come forzare la terminazione).

Esercizi: Dimostrare che DTM ed NDTM accettano la stessa classe di linguaggi.

CH 3 Codifica di una DTM ad un nastro M ed una stringa x ∈ Σ^{∗} (come stringhe di un alfabeto prefissato), DTM universale U (per semplicita’ a piu’ nastri). U=processore, M=programma, x=dati.

Linguaggi/problemi decidibili R (ricorsivi), semidecibili RE (ricorsivamente enumerabili). Esistenza di problemi non-decidibili (e non-semidecidibili) per motivi di cardinalita’; il problema H dell’halt, semidecidibilita’ di H [Prop 3.1], nondecidibile di H [Thm 3.2] tecnica della diagonalizzazione.

Altri problemi non-decidibili [Prop 3.2], riduzione tra problemi L_{1} ≤ L_{2}, proprieta’ di ≤, completezza di H tra i problemi semidecidibili.

Relazioni tra problemi decidibili e semidecidibili [Prop 3.3, 3.4]: R ⊆ RE, L in R implica L̄ in R, L e L̄ in RE implica L in R (tecnica dell’interleaving).

• Mer 22/11/95 (L 12-14) Accenni: caratterizzazione di RE in termini di R, il predicato T di Kleene, la gerarchia aritmetica Σ_{n} e Π_{n} [Ex 3.4.9].

Caratterizzazione alternativa di RE [Prop 3.5] (tecnica del dovetailing).

Linguaggio L(M) accettato da una TM M, proprieta’ “estensionale” di TM {M|L(M) ∈ C}, Teorema di Rice [Thm 3.2].

Altri risultati (senza dimostrazione): Teorema s-m-n [Ex 3.4.6], controparte a livello di linguaggi di programmazione. Esempi di linguaggi in Σ_{1} e Π_{2}.

• Lun 04/12/95 (L 15-16) Proper complexity function [Def 7.1], timers and markers. Semplificazione delle dimostrazioni di alcuni risultati restringendosi a proper complexity functions.

Teorema di gerarchia spazio [enunciato forte]: SP ACE(g) ⊈ SP ACE(f), se g ∉ O(f) e g proper (e g ≥ log). Teorema di gerarchia tempo [enunciato forte]: T IME(g) ⊈ T IME(f), se g ∉ O(f^{2}) e g proper. Gap Theorem [Thm 7.3, senza dimostrazione]: esiste f totale e calcolabile t.c. T IME(f) = T IME(2^{f}).

Classi di complessita’ spazio, tempo, deterministiche e non. coC di una classe di linguaggi. Proprieta’ di chiusura facili (intersezione, unione, complemento), per analogia con R [Ex 7.4.5]. Inclusioni tra classi facili da dimostrare [Thm 7.4]: X(f) ⊆ NX(f), NT IME(f) ⊆ SP ACE(f), NSP ACE(f) ⊆ ∪_{k}T IME(k^{(log n)+f(n)}) tramite reachability method!.

• Mer 06/12/95 (L 17-19) Teorema di Savitch [Thm 7.5]: reachability ∈ SP ACE(log^{2} n), NSP ACE(f) ⊆ SP ACE(f^{2}) (se f proper e f ≥ log), P SP ACE = NP SP ACE.

Classi naturali di complessita’: L, NL, P, NP, P SP ACE, NP SP ACE, EXP = ∪_{k}T IME(2^{n^{k}}).

Dimostrazione dei teoremi di gerarchia (note aggiuntive): codifica con padding delle TM ad un nastro con alfabeto di input prefissato (quello della macchina universale), metodo di diagonalizzazione corretto (nessuna codifica dell’input), uso di una proper g come marker/timer.

Raffinamenti della nozione di riduzione L_{1} ≤ L_{2} per classificare i problemi nelle classi naturali di complessita’: log-space [Def 8.1] e poly-time, problemi complete ed hard. H e’ RE-complete rispetto a riduzioni log-space.

≤_{L}⊆≤_{P} [Prop 8.1]. Transitivita’ di ≤_{L} [Prop 8.2].

• Lun 11/12/95 (L 20-21) Ogni L non banale e’ R-hard rispetto a ≤. Chiusura di classi naturali rispetto a ≤_{L}. Esempi di problemi logici [vedi CH 4]: SAT, circuit value CV P, circuit SAT. Problemi P-completi ed NP-completi tramite varianti di H.

• Mer 13/12/95 (L 22-24) Rappresentazione di computazioni mediante tabelle. P-completezza di CV P e NP-completezza di SAT.

• Lun 18/12/95 (L 25-27) Caratterizzazione di NP con P [Prop 9.1] (analogia con RE).

Varianti di SAT: SAT ≤ 3SAT ∈ NP, 2SAT ∈ NL ⊆ P, HORNSAT ∈ P [Thm 4.2] usa modello di Herbrand, CIRCUIT SAT (riduzione a SAT). SAT ≤ NAESAT ∈ NP (variante di SAT ≤ 3SAT).

Problemi su grafi NP-completi: CLIQUE (e simili), MAXCUT (MINCUT e’ in P), HAMILTON PATH, TSP(D), 3-COLORABILITY.

Problemi su interi: INTEGER PROGRAMMING (linear programming e’ in P), KNAPSACK.

• Mer 20/12/95 (L 28-29) Esercizi: esempi di relazioni tra classi, SP ACE(n)- completezza implica P SP ACE-completezza, esempi di riduzioni, alcune proprieta’ di chiusura.

• Mer 10/01/96 (L 30-31) Descrizione informale di algoritmi probabilistici: RP si e’ certo ma no non lo e’, ZP P si e no sono risposte certe ma puo’ dire non so’, BP P nessuna risposta e’ certa.

NDTM bilanciata: albero binario bilanciato delle computazioni (equiprobabilita’ delle foglie), probabilita’ di una risposta (si, no , non so’).

ZP P: P r[M(x) =?] ≤ 1/2 e x ∈ L ⊃ P r[M(x) = no] = 0 e x ∉ L ⊃ P r[M(x) = yes] = 0

RP: P r[M(x) =?] = 0 e x ∈ L ⊃ P r[M(x) = no] ≤ 1/2 e x ∉ L ⊃ P r[M(x) = yes] = 0

BP P: P r[M(x) =?] = 0 e x ∈ L ⊃ P r[M(x) = no] ≤ 1/4 e x ∉ L ⊃ P r[M(x) = yes] ≤ 1/4

P P: P r[M(x) =?] = 0 e x ∈ L ⊃ P r[M(x) = no] < 1/2 e x ∉ L ⊃ P r[M(x) = yes] < 1/2

Esempi di algoritmi probabilistici (in RP o coRP): A ∗ B = C?, P = 0? con P termine con variabili nel linguaggio degli anelli, p e’ primo? [sta in ZP P, e se vale ERH sta in P] Riformulazione di RP etc usando predicati R calcolati in tempo polinomiale e t.c. R(x, y) ⊃ |y| = p(|x|).

• Lun 15/01/96 (L 32-34) Powering per ZP P, RP e BP P abbassamento della probabilita’ di errore dopo k ripetizioni. No powering per P P. Utilita’ della randomizzazione per abbassare la complessita’ di anche problemi trattabili.

Problemi implementativi: in natura e’ difficile avere eventi casuali indipendenti (ravvicinati nel tempo e nello spazio).

Relazioni tra classi: P ⊆ ZP P ⊆ RP ⊆ BP P ⊆ P P ⊆ P SP ACE, ZP P = RP ∩ coRP e RP ⊂ NP ⊆ P P.

Proprieta’ di chiusura ZP P, RP e BP P: per riduzione, per complemento ZP P e BP P, per unione ed intersezione, mancanza di problemi completi (anche artificiali).

• Mer 17/01/96 (L 35-37) Problemi di ottimizzazione e problemi correlati. Algoritmi di ϵ-approssimazione (asintotici), soglia di approssimazione, schemi di approssimazione (pienamente) polinomiali.

Esempi: node cover, MAXSAT e MAXGSAT, TPS (non approssimabile)

• Lun 22/01/96 (L 38-40) Esempi: KNAPSACK (schema di approssimazione pienamente polinomiale). L-riduzioni e problemi di ottimizzazione, A ≤_{L} B e B ha un (fully) polynomia approx. scheme implica che anche A lo ha.

Esempi di algoritmi paralleli: moltiplicazione di matrici (principio di Brent), reachability e chiusura riflessiva e transitiva di una matrice (booleana), prefix sum. Confronto tra tempo sequenziale, tempo parallelo e lavoro.

• Mer 24/01/96 (L 41-42) Riprendere prefix sum problem: generalizzazione ad operazioni associative, adattamento per l’addizione di numeri binari d n bits in PT O(log n) [moltiplicazione e trucco del due per tre].

Modello di calcolo parallelo basato su famiglie uniformi di circuiti booleani. Size e depth di un circuito (anche con piu’ output), alcune inadeguatezze: costo delle comunicazioni (quanto sono lunghi i cavi?). La classe P T/W K(f, g): UNIFORM family of circuits con depth O(f) e size O(g).

Perche’ uniformity [Thm 11.5]: L ∈ P sse L e’ calcolato da una famiglia uniforme di circuiti booleane.

Nick class NC_{j} = ∪_{k}P T/W K(log^{j}, n^{k}) e NC = ∪_{j}NC_{j}.

L ⊆ NL ⊆ NC_{2}, chiusura di NC_{j} (j ≥ 2) rispetto alla L-riduzione. Problemi P -completi (p.e. e’ poco probabile che siano in NC, e’ poco probabile che esista un problema NC-completo, perche’ implicherebbe che NC = NC_{j}.

• Ven 26/01/96 (L 43-44) Tecnica dello scaling back quando il numero di processori disponibili e minore di quelli necessari per parallelizzare al massimo l’algoritmo. Impossibilita’ di risolvere problemi non trattabili con algoritmi paralleli (tempo e processori polinomiali).

Stabilita’ di NC rispetto a cambio di modello: correlazione tra uniform PRAM P_{m,n} (multiprocessore a memoria condivisa) e circuiti booleani: Se F e’ camcolata da una PRAM in tempo f(n) e numero di processori q(m, n) ≤ g(n) [con f e g calcolate in logspace con input 1^{n}] allora F ∈ P T/W K(f(n)(f(n) + log n), g(n)f(n)(n^{k}f(n) + g(n))).