Teaching plan for the course unit



Close imatge de maquetació




General information


Course unit name: Computational Complexity

Course unit code: 569077

Academic year: 2021-2022

Coordinator: Joost Johannes Joosten

Department: Faculty of Philosophy

Credits: 6

Single program: S

More information enllaç



Estimated learning time

Total number of hours 150


Face-to-face and/or online activities



-  Lecture





-  Lecture with practical component





-  Problem-solving class




Supervised project


(eight times five homework sessions)

Independent learning




Competences to be gained during study



Technical Competences of each Specialization

Advanced computing

  • CEE3.1 - Capability to identify computational barriers and to analyze the complexity of computational problems in different areas of science and technology as well as to represent high complexity problems in mathematical structures which can be treated effectively with algorithmic schemes. 
  • CEE3.3 - Capability to understand the computational requirements of problems from non-informatics disciplines and to make significant contributions in multidisciplinary teams that use computing. 


Generic Technical Competences


  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions. 
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science. 

Transversal Competences


  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation. 


  • CB8 - Capability to communicate their conclusions, and the knowledge and rationale underpinning these, to both skilled and unskilled public in a clear and unambiguous way. 
  • CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous. 





Learning objectives


Referring to knowledge

  1. Understand different computational models and there interrelations.
  2. Understand the concept of (space, time) complexity classes (deterministic, non-deterministic, probabilistic).
  3. Understand Lower Bounds in Circuit Complexity and their importance.
  4. Understand the impact of computational complexity, both to theoretical computer science and to applied computer science.


Referring to abilities, skills

  1. Be able to identify inherent computational barriers.
  2. Be able to model computational processes and analyze the complexity of computational problems.
  3. Know how to use the main pointers in the literature and be able to place a paper in the literature landscape.
  4. Consolidate the previously defined competences and being able to apply them in various contexts both pure and applied.


Referring to attitudes, values and norms

  1. Lose fear of complex processes and acquire an attitude to start analyzing the most important (or understandable) parts of these processes.
  2. Acquire the norm to place scientific activities and contributions within the literature landscape with due references to the main contributors.



Teaching blocks


1. Computational Models and Complexity Measures


  1. Turing machine model. RAM model.
  2. Boolean circuit model.
  3. Time complexity.
  4.  Space complexity.
  5. Circuit size.
  6. Circuit depth.
  7. Time and space hierarchy theorems.

2. P, NP and NP-completeness


  1. Polynomial time. 
  2. Reducibilities.
  3. Non-deterministic algorithms and class NP.
  4. Cook-Levin Theorem. 
  5. Many other NP-complete problems.

3. Polynomial-time Hierarchy and Alternations


  1. Oracle reducibility.
  2. NP and co-NP.
  3. Levels of the hierarchy.
  4. Quantifier alternations.
  5. Complete problems.

4. Space Complexity


  1. Polynomial space.
  2. Unbounded alternations.
  3. PSPACE-complete problems.
  4. Savitch Theorem.
  5. Immerman-Szcelepscenyi Theorem.
  6. Logarithmic space. 
  7. NL-complete problems.

5. Randomized Computation


  1. Bounded-error and zero-error probabilistic polynomial time. 
  2. Error-reduction.
  3. Randomized reductions. 
  4. Valiant-Vazirani reduction to Unique SAT.

6. Counting and Enumeration


  1. Some examples: graph reliability, counting matchings and the permanent, partition functions.
  2. Counting computation paths in non-deterministic machines. 
  3. Valiant’s Theorem.
  4. Random self-reducibility of the permanent.

7. Probabilistic Proofs


  1. Interaction and randomness in proofs.
  2. Probabilistic proofs for graph non-isomorphism. 
  3. Probabilistic proofs for #P and Shamir’s Theorem: IP = PSPACE.

8. Circuit Lower Bounds


  1. Monotone circuits.
  2. Lower bounds for clique and perfect matching.
  3. Bounded-depth circuits. 
  4. Hastad’s switching lemma.
  5. 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 on-line 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).
There will be a final exam graded in [0,10] (E).
The final grade of the course will be MAX(P1+P2+P3+P4+P5+E/2, E).

The problem/discussion sheets will consist of problems from the main textbook [Arora-Barak] and/or multiple choice questions that test if the student understood the material from the theory class (also covered in the main textbook).


Examination-based assessment

There will be a final exam graded in [0,10]



Reading and study resources

Consulteu la disponibilitat a CERCABIB


  • Computational complexity: a modern approach - Arora, S.; Barak, B, Cambridge University Press, 2009. ISBN: 9780521424264  
  • Computational complexity - Papadimitriou, C.H, Addison-Wesley , 1994. ISBN: 0201530821 
  • Computational complexity: a conceptual perspective - Goldreich, O, Cambridge University Press , 2008. ISBN: 9780521884730 

Computational complexity: a modern approach   Enllaç
Computational complexity  Enllaç
Computational complexity: a conceptual perspective   Enllaç