Computer Science - Informatica

MASSIMO LAURIA

Obiettivi generali:
Il Corso introduce allo studio delle basi della Teoria della Complessità computazionale.

Obiettivi specifici:
- Concetto teorico della risorsa computazionale: running time
- Concetto Teorico della risorsa computazionale: memoria
- Classi di complessità temporali e spaziali
- Il problema P = NP
- Problemi computazionalmente non trattabili con risorse limitate
- La classi di complessità L, P, NP, PSPACE, BPP, #P, IP,
- Risultati Notevoli
- Circuiti Booleani e funzioni booleane

Conoscenza e comprensione:
Al termine del corso lo studente avrà acquisito la capacità di verificare proprietà di riduzione e completezza tra problemi computazionali, la conoscenza di teoremi notevoli nel campo della Teoria delle Complessità, la capacità di ragionare matematicamente sulla natura computazionale delle risorse di calcolo come running-time, memoria, randomness.

Applicazione di conoscenza e comprensione:
La conoscenza appresa è fondamentale in contesti come la Verifica Automatica, la Teoria dei Giochi, la analisi della complessità degli algoritmi.

Autonomia di giudizio:
Viene rafforzata la autonomia di giudizio dello studente attraverso l'approfondimento
della capacità di sintesi matematica, di ragionamento matematico e di problem solving, mediante tecniche basate sulla matematica Discreta e sulla Analisi Funzionale.

Abilità comunicative:
Viene sviluppata l'abilità comunicativa dello studente nel presentare risultati nel campo dell'Informatica Teorica.

Capacità di apprendimento:
La complessità computazionale e alla base della comprensione della valutazione della fattibilità computazionale e algoritmico di qualsiasi
problema del mondo reale. La sua conoscenza è dunque alla base dell'apprendimento di molte altre corsi e argomenti, come la Crittografia, la verifica automatica del software e dell'hardware, la Teoria dei Giochi, l'Intelligenza Artificiale.

PREREQUISTI ITA
Concetti di base di Matematica Discreta (conteggi, grafi, permutazioni, ) [importante]
Concetti di algoritmo e di strutture dati (pile, code, alberi)[importante]
Algoritmi efficienti in presenza di informazioni aggiuntive (esempio ricerca binaria) [importante]
Nozioni di base di Logica proposizionale[importante]
Concetto di Relazione di arità generica[importante]
Concetti di Quantificatore esistenziale ed universale[importante]
Nozioni di base di Logica del primo ordine [importante]
Nozioni di Linguaggi[importante]
Modelli di computazione [importante]
Nozioni di Base di Complessità [importante]

Questo è il programma dell'anno precedente. Il programma potrà subire variazioni.

_________________________________________________

SYLLABUS OF "COMPUTAIONAL COMPLEXITY 2022/2023"

Massimo Lauria
_________________________________________________





1 Bibliography
==============

The main textbook of the course is

- [AB] Arora, Barak. /Computational Complexity: A Modern Approach/.
Cambridge University Press, 2007.

Additional material on communication complexity and proof complexity
are in

- [J] Jukna. /Boolean Function Complexity/. Springer, 2012.
- [RY] Rao, Yehudayoff. /Communication Complexity and Applications/.
Cambridge University Press, 2020.

A proof from the last part of the course is only published, as far as
I know, in
- [K] Knuth, the Art of Computer Programming, Vol 4, fascicle 6, Page
55-56.

All reference to a textbook refer to book [AB] unless
specified otherwise.


2 Introduction
==============

- Introduction
- Chapter 0
- Parity on n variables requires CNF formulas of size Theta(n 2^n)
- Equality of two strings of n bits requires n bits of
communication


3 Turing machines, Universality, Uncomputability, the class P
=============================================================

- Sections 1.1, 1.2, 1.3, 1.4
- Sections 1.5, 1.6
- Exercises 1.2, 1.3, 1.5, 1.8, 1.14
- Read and ponder the statement of Exercise 1.6, 1.7 and 1.9


4 NP and NP-completeness
========================

- Karp reductions
- NP-completeness
- Non deterministic Turing Machines
- Cook-Levin theorem proved via Circuit-SAT (see Section 6.1)
- Decision vs Seach
- coNP, EXP, NEXP
- Implications of P vs NP
- Sections 2.1, 2.2, 2.3 (Section 2.3.4 is optional), 2.4, 2.5, 2.6,
2.7
- Section 6.1
- Exercises 2.1, 2.2, 2.4, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11, 2.12, 2.14,
2.15, 2.16, 2.17, 2.18, 2.21, 2.23, 2.24, 2.25, 2.26, 2.27, 2.29,
2.30, 2.31, 2.34.


5 Time Hierarchy Theorems, Oracles
==================================

- Hierarchy theorem for deterministic time
- Hierarchy theorem for non-deterministic time (just the statement)
- Ladner theorem (just the statement)
- Turing Machines with oracles
- P vs NP does not relativize w.r.t. to Oracles
- Sections 3.1, 3.2, 3.3, 3.4


6 Space complexity, NL-completeness
===================================

- The Graph of configurations
- PSPACE, TQBF is PSPACE-complete
- Savitch's Theorem
- Lospace reductions and NL-completeness
- NL = coNL
- Sections 4.1, 4.2, 4.3
- Exercises 4.1, 4.2, 4.4, 4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.11


7 Randomized computation, RP, coRP, BPP, ZPP
============================================

- Appendix A.2
- Sections 7.1, 7.2 (no 7.2.4), 7.3, 7.4, 7.5 (no 7.5.3)
- Exercises 7.1, 7.4, 7.5, 7.6


8 Interactive Proofs and PSPACE
===============================

- randomness in interaction is necessary
- public vs private randomness
- IP, AM, MA classes
- protocol for Graph Non Isomorphism
- coNP \(\in\) IP
- IP = PSPACE
- Sections 8.1, 8.2, 8.3
- Sections 8.2.2 and 8.2.3 are optional, but the statement of Theorems
8.12 and 8.13 are part of the program
- Exercises 8.1, 8.2, 8.6, 8.8


9 Circuits and Polynomial Hierarchy
===================================

- BPP vs P/poly
- BPP in the second level of the hierarchy
- Karp-Lipton theorem
- if GI is NP-complete, then PH collapses to second level
- Circuit size complexity
- Theorem 1.29 on Jukna's book [J]
- Sections 5.1, 5.2, 6.1, 6.2, 6.4, 6.5, 6.6, 7.5, 8.2.4
- Exercises 5.1, 6.3, 6.5, 6.6


10 Decision trees
=================

- decision trees
- worst case depth complexity
- certificate complexity
- just the statement that bs(f)

Testi principali:

S. Arora B. Barak: Computational Complexity: A Modern Approach Cambridge University Press, 2007
S. Jukna. Boolean Function Complexity. Springer. 2012
A.Rao, A. Yehudayoff. Communication Complexity and Applications. Cambridge University Press, 2020

Altri testi complementari

E. Kushilevitz & N. Nisan. Communication Complexity. Cambridge University Press 2006.
O. Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity Cambridge University Press 2010
O. Goldreich. Computational Complexity: A Conceptual Perspective Cambridge University Press 2008.
A. Wigderson. Mathematics and Computation. Princeton University Press. 2019
C. Papadimitriou. Computational Complexity. Pearsons. 1994.
H. Vollmer. Introduction to Circuit Complexity: an uniform approach, Springer. 2013
J. Krajicek. Proof Complexity. Cambridge. 2019.

Le lezioni saranno in presenza, frontali e in aula. Non ci saranno registrazioni.
Ci saranno (come parte della valutazione finale) delle presentazioni di studenti

La frequenza è consigliata fortemente ma non è obbligatoria.
Comunque ci saranno delle presentazioni da fare in aula per la valutazione finale.

1.Presentazione alla lavagna di risultati semplici (durante il corso)
2. Compito per casa di metà corso
3. Prova orale finale

Presentare la dimostrazione del teorema di Cook.

Nella definizione di BPP, qual è il range accettabile per la probabilità trovare la risposta corretta?