General information 
Course unit name: Computational Complexity
Course unit code: 569077
Academic year: 20212022
Coordinator: Joost Johannes Joosten
Department: Faculty of Philosophy
Credits: 6
Single program: S
Estimated learning time 
Total number of hours 150 
Facetoface and/or online activities 
56 
 Lecture 
Facetoface 
28 

 Lecture with practical component 
Facetoface 
14 

 Problemsolving class 
Facetoface 
14 
Supervised project 
40 
(eight times five homework sessions) 
Independent learning 
54 
Competences to be gained during study 
CompetencesTechnical Competences of each SpecializationAdvanced computing
Generic Technical CompetencesGeneric
Transversal CompetencesReasoning
Basic

Learning objectives 
Referring to knowledge
Referring to abilities, skills
Referring to attitudes, values and norms

Teaching blocks 
1. Computational Models and Complexity Measures
*
 Turing machine model. RAM model.
 Boolean circuit model.
 Time complexity.
 Space complexity.
 Circuit size.
 Circuit depth.
 Time and space hierarchy theorems.
2. P, NP and NPcompleteness
*
 Polynomial time.
 Reducibilities.
 Nondeterministic algorithms and class NP.
 CookLevin Theorem.
 Many other NPcomplete problems.
3. Polynomialtime Hierarchy and Alternations
*
 Oracle reducibility.
 NP and coNP.
 Levels of the hierarchy.
 Quantifier alternations.
 Complete problems.
4. Space Complexity
*
 Polynomial space.
 Unbounded alternations.
 PSPACEcomplete problems.
 Savitch Theorem.
 ImmermanSzcelepscenyi Theorem.
 Logarithmic space.
 NLcomplete problems.
5. Randomized Computation
*
 Boundederror and zeroerror probabilistic polynomial time.
 Errorreduction.
 Randomized reductions.
 ValiantVazirani reduction to Unique SAT.
6. Counting and Enumeration
*
 Some examples: graph reliability, counting matchings and the permanent, partition functions.
 Counting computation paths in nondeterministic machines.
 Valiant’s Theorem.
 Random selfreducibility of the permanent.
7. Probabilistic Proofs
*
 Interaction and randomness in proofs.
 Probabilistic proofs for graph nonisomorphism.
 Probabilistic proofs for #P and Shamir’s Theorem: IP = PSPACE.
8. Circuit Lower Bounds
*
 Monotone circuits.
 Lower bounds for clique and perfect matching.
 Boundeddepth circuits.
 Hastad’s switching lemma.
 Approximation by polynomials.
Teaching methods and general organization 
Blackboard lectures for theory classes and discussion sessions for the problem classes. The theory classes will follow the main textbook for the class [Arora and Barak] rather closely. Since we plan to cover more topics than is possible in the given time, students will be required to read the details in the textbook as homework (a draft of the book is available online for free). The aim of the discussion sessions is to solve some problems from that book and to discuss the reading material. 
Official assessment of learning outcomes 
Students will be required to submit 5 problem/discussion sheets. Each will be given a grade in [0,1] (P1,...,P5).
Examinationbased assessment There will be a final exam graded in [0,10] 
Reading and study resources 
Consulteu la disponibilitat a CERCABIB
Book
Computational complexity: a modern approach
Computational complexity
Computational complexity: a conceptual perspective