Computational Complexity

6 EC

Semester 2, period 4

5314COCO6Y

Owner Master Logic
Coordinator dr. Ronald de Haan
Part of Master Logic, Master Logic, track Logic and Computation, Master Logic, track Logic and Philosophy, Master Logic, track Logic and Language, Master Logic, track Logic and Mathematics, Master Computer Science (joint degree), track Foundations of Computing and Concurrency, Master Computer Science (joint degree), track Software Engineering & Green IT, Master Computer Science (joint degree), track Big Data Engineering, Master Mathematics, specialization Mathematical Physics, year 1Master Computer Science (joint degree), track Computer Systems and Infrastructure, year 1Master Computer Science (joint degree), track Systems for Large-scale Applications, year 1Master Quantum Computer Science,

Course manual 2025/2026

Course content

Complexity theory deals with the fundamental question of how many resources, such as time, memory, communication, randomness, etc., are needed to perform a computational task. A fundamental open problem in the area is the well-known P versus NP problem, one of the Clay Millennium problems. In this course we will treat the basics of complexity theory, NP-completeness, diagonalisation, Boolean circuits, randomised computation, interactive proofs, cryptography, quantum computing, and circuit lower bounds.

Study materials

Literature

  • S. Arora and B. Barak. 'Computational Complexity: A Modern Approach'. Cambridge University Press, 2009.

Objectives

  • Compare different models of resource-bounded computation.
  • Analyze the running time of an algorithm in terms of the input size.
  • Formulate how a computational task can be modeled as a decision problem.
  • Argue why the approach of distinguishing different complexity classes is useful.
  • Critize the framework of worst-case asymptotic complexity analysis.
  • Explain the concepts of nondeterminism, alternation, and randomized algorithms.
  • Produce a proof of NP-completeness for variants of known NP-complete problems.
  • Predict what the implications are if certain complexity classes coincide.
  • Classify the location of a decision problem in the landscape of computational complexity.
  • Explain how oracles can be used to show the limits of relativizing proofs, and what constraints this places on any proof for P != NP.
  • Explain how various complexity-theoretic assumptions (e.g., P != NP, Exponential Time Hypothesis) can be used to rule out efficient algorithms for computational problems.

Teaching methods

  • Lecture
  • Seminar
  • Self-study

Lectures and exercise sessions.

Learning activities

Activity

Number of hours

Zelfstudie

168

Attendance

This programme does not have requirements concerning attendance (TER-B).

Assessment

Item and weight Details

Final grade

1 (100%)

Homework assignment 2

Assignments

There are three homework assignments, that may be done individually or in pairs. In addition, there is a final take-home exam, that is to be done individually.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Weeknummer Onderwerpen Studiestof
1
2
3
4
5
6
7
8

Additional information

Prerequisites: Basic math and computer science.

Contact information

Coordinator

  • dr. Ronald de Haan