Computational Complexity

You are here

Home » Studies » Masters » Master in Innovation and Research in Informatics » Curriculum » Syllabus » Computational Complexity
Credits
6
Types
Specialization compulsory (Advanced Computing)
Requirements
This subject has not requirements
Department
CS
The theory of computational complexity provides tools for analysing the minimal amount of computational resources that are needed for algorithmically solving a problem. The classical resources that are studied are time and memory usage, but more recent developments have shown that several other computational resources are equally relevant, such as the amount of randomness needed by the algorithm, or the depth of the circuit that implements the algorithm as a measure of its parallelism. Besides introducing the basics of the theory, in this course we will spend some time discussing the relevance of the famous P vs. NP problem and its relatives to computer science and technology, but also its relevance to other areas of science.

Syllabus: Models of computation and computational resources: time, space, randomness, circuit-depth and circuit-size. Basic complexity classes, reductions and completeness, P vs. NP problem. Randomness as a resource and tool, probabilistic proof systems. Complexity of sampling and combinatorial counting problems. Advanced topics: circuit lower bounds, derandomization, PCP-theorem and inapproximability.

Teachers

Person in charge

  • Albert Atserias Peri ( )

Others

  • Antoni Lozano Boixadors ( )

Weekly hours

Theory
2
Problems
2
Laboratory
0
Guided learning
0
Autonomous learning
4

Competences

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

Generic

  • 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

Reasoning

  • 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.

Basic

  • 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.

Contents

  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 NP-completeness
    Polynomial time. Reducibilities. Non-deterministic algorithms and class NP. Cook-Levin Theorem. Many other NP-complete problems.
  3. Polynomial-time Hierarchy and Alternations
    Oracle reducibility. NP and co-NP. Levels of the hierarchy. Quantifier alternations. Complete problems.
  4. Space Complexity
    Polynomial space. Unbounded alternations. PSPACE-complete problems.
    Savitch Theorem. Immerman-Szcelepscenyi Theorem.
    Logarithmic space. NL-complete problems.
  5. Randomized Computation
    Bounded-error and zero-error probabilistic polynomial time. Error-reduction.
    Randomized reductions. Valiant-Vazirani reduction to Unique SAT.
  6. Counting and Enumeration
    Some examples: graph reliability, counting matchings and the permanent, partition functions.
    Counting computation paths in non-deterministic machines. Valiant's Theorem.
    Random self-reducibility of the permanent.
  7. Probabilistic Proofs
    Interaction and randomness in proofs. Probabilistic proofs for graph non-isomorphism. Probabilistic proofs for #P and
    Shamir's Theorem: IP = PSPACE.
  8. Circuit Lower Bounds
    Monotone circuits. Lower bounds for clique and perfect matching.
    Bounded-depth circuits. Hastad's switching lemma.
    Approximation by polynomials.

Activities

Activity Evaluation act


Submission first problems sheet



Week: 3
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Submission second problems sheet



Week: 6
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Submission third problems sheet



Week: 9
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Submission forth problems sheet



Week: 12
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Submission fifth problems sheet



Week: 15
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Final exam



Week: 18
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
12h

Teaching methodology

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.

Evaluation methodology

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).

Bibliography

Basic:

Complementary: