Computational Complexity

6 EC

Semester 2, period 5

5314COCO6Y

Owner Master Logic
Coordinator dr. Ronald de Haan
Part of Master Logic, Master Logic, track Logic and Computation, 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 Mathematics, specialisation Discrete Mathematics and Quantum Information, year 1Master Computer Science (joint degree), track Computer Systems and Infrastructure, year 1Master Computer Science (joint degree), track Systems for Large-scale Applications, year 1

Course manual 2023/2024

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
  • Self-study
  • Seminar

In the lectures, we will cover the main theoretical tools that are used. In the exercise sessions, students will engage with the material in order to deepen their understanding.

Learning activities

Activity

Number of hours

Lectures

26

Exercise sessions

12

Self study

130

Attendance

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

Additional requirements for this course:

There is no mandatory attendance.

Assessment

Item and weight Details

Final grade

1 (17%)

Homework assignment 1

1 (17%)

Homework assignment 2

1 (17%)

Homework assignment 3

3 (50%)

Take-home exam

NAP if missing

Feedback on the homework assignment is given via Canvas.

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

The course structure can be found here: https://staff.science.uva.nl/r.dehaan/complexity2024/

Contact information

Coordinator

  • dr. Ronald de Haan