Computational Complexity

2026-10-13

Continue the discussion of the polynomial hierarchy, the notion of collapse, and we prove Theorem 6.6: (Karp-Lipton) implies We state the claim that Graph Isomorphism is likely not to be NP-complete. We define the classes RP, coRP, ZPP and we discuss the amplification of confidence of the algorithm by repetition. We give another randomized algorithms: polynomial identity testing and bipartite matching. Requirements: Appendix A.2 Homework Sections 7.2, 7.3

2026-10-07

We discuss a PSPACE complete problem TQBF and its relation with two-players competitive games. See exercise 4.10. We go on defining the polynomial hierarchy. We discuss the definition (a finite number of alternations) and the absence of a complete problem. We look at Theorem 6.6: (Karp-Lipton) implies We state the claim that Graph Isomorphism is likely not to be NP-complete. Homework Section: 4.2 Sections: 5.1, 5.2 Exercises 5.1, 5.12, 6.5, 6.6 Homework Exercises 4.10

2026-10-06

We review the notion of space complexity. This is the study of how much memory is needed to decide a language. A core concept is the configuration graph of a (non)-deterministic computation. A machine accept if and only if the accepting configuration is reachable in that graph. Review Claim 4.4 and space hierarchy theorem. We also review logspace reductions and the theory of NL-completeness of Reachability. Recall: L is strictly contained in PSPACE Savitch's theorem (Thm 4.14) which implies PSPACE=NPSPACE Immerman-Szelepcsényi (Thm 4.20) which implies NL=coNL Going deeper: Alternative definition of NL and comparison with NP can you check a sat assignment of 3-CNF with one-directional access to the witness? Observe that 3-SAT is NP-complete with respect of logspace reductions.

2026-09-30

We discuss the concept of non-uniformity: to compute a function we need a circuit class with an infinite description. Is this process always constructive? We analyze this with the language of machines with advices. The we start a recap of NP-completeness theory, in order to prove the Cook-Levin theorem. Homework Section 6.1.2, 6.2, 6.3 [AB] [pdf] Complexity classes, NP and Cook-Levin

2026-09-29

We prove that the number of OR and AND gates in a circuit for Parity on n bits is exactly 3n-3. We give a brief recap about Turing machine, and we enumerate the properties needed to prove that efficient TMs imply small circuits (Theorem 6.6 in [AB]). Homework Section 6.1, and 6.1.1 specifically [AB] Theorem 1.29 [J] [pdf] Turing machine recap lecture notes

2026-09-23

Introduction of the course, and of the topic of computational complexity. We discussed generically what it means to prove a lower bound, i.e., to show that it is impossible to compute some function within a certain amount of resources. An impossibility result is a mathematical statement about a computational model. We can focus on powerful computational model and only prove weak and conditional lower bounds, and we can consider concrete and restricted models where we can prove tight one. We saw the example of two lower bounds: Parity on variables requires CNF formulas of size theta(n*2^n) (Sketch) Equality of two strings of n bits requires n bits of communication. We introduce boolean circuits. We give the general upper bound O(2^n) for every boolean function, and we clain without proof the Shannon upper bound O(2^n/n), which is then compared with a matching lower bound for almost all functions. even though we do not know how they look like. Then we show a hierarchy theorem for circuits. After that we show the minimum number of OR and AND gates in a circuit for Parity on n bits is exactly 3n-3 Homework: read Introduction and Chapter 0 of textbook [AB] Section 6.1 [AB]

Senza scadenza

Senza scadenza

Scadenza: 2026-10-09

Senza scadenza