NP Completezza (CLRS, Cap. 34)

• Presentazione ragionata del corso. Programma preliminare.
• Classi di problemi: problemi indecidibili, intrinsecamente esponenziali, intrattabili, polinomiali.
• Problemi astratti e problemi decisionali. Riduzione da problemi di ottimizzazione a problemi decisionali. Esempio: SHORTEST UNWEIGHTED PATH.
• Il problema dell'encoding: problemi astratti e problemi concreti.

• Encoding ragionevoli.
• Linguaggi formali. Problemi concreti e linguaggi associati.
• Decisione di un linguaggio in tempo polinomiale: la classe P: definizione.
• Verificabilità in tempo polinomiale: introduzione.
• Algoritmo di verifica per HAMILTON.
• Verificabilità in tempo polinomiale: definizione.
• La classe NP. Teorema: P è un sottoinsieme di NP.
• Riducibilità: HAMILTON e TSP

• Riducibilità in tempo polinomiale.
• Caratteristiche delle funzioni di riduzione.
• Teorema: Se L1 < L2 e L2 è in P, allora L1 è in P.
• Le classi NPH e NPC.
• Corollario: se L e' sia in NPC che in P, allora P=NP.
• Il problema BC-SAT. Definizione.
• Il teorema di Cook: 1) Algoritmo di verifica polinomiale per BC-SAT. 2) Riduzione di ogni linguaggio in NP a BC-SAT (idea della riduzione).

• Il teorema di Cook: prova.
• Il problema FORMULA-SAT. Definizione. Riduzione non polinomiale da BC-SAT.
• Riduzione polinomiale da BC-SAT a FORMULA-SAT.

• Il problema 3CNF-SAT. Riduzione da BC-SAT.
• Il problema CLIQUE. Definizione e riduzione da 3CNF-SAT.
• Definizione dei problemi VERTEX-COVER e INDEPENDENT-SET.

• VERTEX-COVER e INDEPENDENT-SET: riduzioni da CLIQUE.
• Il problema SUBSET SUM. Definizione e riduzione da 3CNF-SAT.
• Esercizio: Difficoltà del Testing di Circuiti Booleani.

• Oggni linguaggio in NP ammette decisione (esponenziale)
• HALTING problem è in NPH
• Proprietà dei linguaggi complementari e la classe Co-NP
• KNAPSACK problem è in NPC

• Costruzione di una soluzione a partire da un oracolo per il problema decisionale: applicazione a SUBSET-SUM
• LONG-PATH problem è in NPC
• DOMINATING SET problem è in NPC

• Schemi di approssimazione polinomiali e pienamente polinomiali (PTAS e FPTAS)
• Algoritmo di 2-approssimazione per VERTEX COVER: definizione e analisi.
• Inefficiacia dell'algoritmo per il calcolo di una clique.
• Spiegazione informale: le riduzioni in tempo polinomiale non preservano l'approssimazione.

• TSP: definizione e NP-Completezza
• Inapprossimabilità del TSP generale
• Definizione di TRIANGLE-TSP e prova di NP-completezza
• Algoritmo di 2-approssimazione per TRIANGLE-TSP

• Algoritmo di Christofides per la 3/2-approssimazione di TRIANGLE-TSP
• Cenni ai risultati di inapprossimabilità per TRIANGLE-TSP
• Cenni all'approssimabilità di EUCLIDEAN-TSP

• Definizione del problema SET-COVER e NP-completezza.
• Analisi di log-approssimazione per SET-COVER
• Analisi più fine per SET-COVER

• FPTAS per SUBSET-SUM: l'algoritmo enumerativo.
• FPTAS per SUBSET-SUM: l'algoritmo approssimato.
• FPTAS per SUBSET-SUM: determinazione del fattore di approssimazione.

• FPTAS per SUBSET-SUM: complessita' in tempo.
• Approssmazione randomizzata: definizione.
• MAX-SAT. Definizione, NP-completezza e algoritmo randomizzato di 8/7 approssimazione.
• Tecnica del rilassamento lineare e del rounding: applicazione a weighted vertex cover.

• Identità di Bezout.
• L'algoritmo di Euclide: correttezza.
• L'algoritmo di Euclide: complessità.
• L'algoritmo di Euclide Esteso: : correttezza e complessità.

• Aritmetica modulare: la struttura quoziente Zn: definizione e proprietà di gruppo rispetto alla somma.
• Il sottoinsieme Z*n: definizione
• Z*n è un gruppo moltiplicativo. Calcolo dell'inverso con EXTENDED-EUCLID.
• La funzione di Eulero. Il teorema di Eulero e il piccolo teorema di Fermat.
• Il Teorema cinese dei resti: enunciato

• Il Teorema cinese dei resti: prova e corollari
• Definizione di criptosistema e criptosistema a chiave pubblica.
• Dettagli di RSA: calcolo della chiave pubblica e della chiave segreta: algoritmo cubico basato sull'esponenziazione veloce.
• Protocolli di comunicazione e autenticazione.
• Prova di correttezza: la funzione di codifica e decofica sono una l'inversa dell'altra.

• Attacchi a RSA.
  1. Decomposizione di n=pq se p e q sono molto vicini tra loro.
  2. Attacchi per scelte di chiavi pubbliche con lo stesso esponente.
  3. Attacchi per scelte di chiavi pubbliche con lo stesso modulo.
  4. Attacchi basati sull'autenticazione

• Pseudoprimi in base a e test semplice per numeri casuali. I numeri di Carmichael.
• Estrazione casuale di primi: il teorema di Pomerance e analisi probabilistica dell'algoritmo basato sul test di pseudoprimalità in base 2.
• Esponenziazione modulare e radici quadrate non banali dell'unità
• Il test randomizzato di Miller-Rabin. Certificato di nonprimalità basato sul teorema di Fermat e sull'esistenza di una radice quadrata non banale dell'unità. Complessità.

• Miller-Rabin: analisi della correttezza per numeri non di Carmichael.

• Introduzione agli algoritmi randomizzati: algoritmi Monte Carlo e Las Vegas.
• Analisi in media e in alta probabilità
• Le diseguaglianze di Markov e implicazioni rispetto all'analisi al caso medio.
• I bound di Chernoff sulla distribuzione di probabilità di somme di Bernoulliane.

• Il bound di Chernoff: enunciati equivalenti.
• Introduzione a Quicksort randomizzato: intuizione sull'efficienza computazionale
• Applicazione dei bound di Chernoff all'analisi in alta probabilità di Quicksort
• Analisi al caso medio di Quicksort tramite la seconda diseguaglianza di Markov

• Definizione del problema del taglio minimo su multigrafi
• Definizione di contrazione di un multigrafo rispetto a un arco e proprieà rispetto ai tagli.
• L'algoritmo di Min-Cut di Karger: codice

• L'algoritmo di Min-Cut di Karger: analisi
• L'algoritmo di Min-Cut di Karger-Stein: descrizione e analisi della strategia divide-and-conquer

Lezioni soppresse per missione all'estero del docente.

• Il problema del polling
• Il problema del coupon collecting
• Generazione di bit senza bias da bit con bias
• Approssimazione randomizzata: Independent Set

• Estrazione degli elementi frequenti da uno stream di n elementi (n noto)
• Estrazione degli elementi frequenti da uno stream di n elementi (n non noto): lo sticky sampling

• Calcolo del numero di elementi distinti di uno stream: probabilistic counters e median trick.

Esercitazioni su tutti gli argomenti trattati durante il corso

Presentazioni delle tesine di esonero