Computer Science

MASSIMO LAURIA
MASSIMO LAURIA

General goals:
This represents a basic course about the Theory of Computational Complexity

Specific goals:
- Theoretical model of resource running time
- Theoretical model of resource memory occupation
- Time and Space complexity classes
- The P = NP problem
- Unfeasible problems when resources are bounded
- Computational Classes L, P, NP, PSPACE, BPP, #P, IP,
- Main Results
- Boolean Circuit and functions

Knowledge and understanding:
The student will acquire:
1. The ability to verify reduction and completeness properties between computational problems.
2. Knowledge of the main theorems in the field of Complexity Theory
3. Capabilities of mathematical reasoning on the computational nature of computational resources like running-time, memory occupation, randomness

Applying knowledge and understanding:
The knowledge acquired is basic and foundational in fields like Software Verification, Game Theory, Analysis of Algorithms

Critical and judgmental skills:
Enabling autonomous thinking in students by deepening their ability of mathematical reasoning through the development of discrete math techniques and functional analysis abilities.

Communication skills:
Developing students' ability to communicate advanced results in the field of Theoretical computer Science

Ability of learning:
Knowledge about Computational Complexity is necessary to evaluate the computational viability of the solution of any computational problem arising in the real world. Its knowledge is hence fundamental and basic in many Computer Science disciplines like Cryptography, Verification, Artificial Intelligence, Game Theory.

The goal is to make the students understand the theoretical analysis of computation, in order to be able to adress and understand fundamental questions about computation and its efficiency. The students would improve the ability to prove mathematical theorems that answer or frame problems in computation.

Basic notions of discrete mathematics (counting, graphs, permutations, ) [important]
Notion of algorithm and data structure (Stack, queue, trees)[important]
Efficient algorithms exploiting data information (for instance, binary search)[important]
Basic notions of propositional logic [important]
Notion of Relation of generic arity[important]
Notion of universal and existential Quantification[important]
Concetto di Relazione di arità generica[important]
Basic notions of first order Logic[important]
Advanced Notions on Languages [important]
Computational models [important]
Basic Notions of Complexity Theory [importante]

This is the 2025/2026 syllabus. The syllabus may change, depending on the pace of the couse.

_________________________________________________

SYLLABUS OF "COMPUTAIONAL COMPLEXITY 2025/2026"

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)

Main textbooks:

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

Other reference textbooks

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.

Lecture will be live in class, with no recording whatsoever.
There will be student presentations, as part of the final evaluation.

Attending is not mandatory, but strongly suggested.
Nevertheless there will be a mandatory presentation in front of the class, which contributes to the final grade.

1. I quarter term blackboard presentations of a basic result.
2. Half-term homeworks
3. Final oral examinations.

Present the proof of Cook's Theorem

In the definition of BPP, what is the acceptable range for the probability of finding the right answer?