# Computability and Complexity (CoCo)

### Course content

Computers are everywhere today—at work, in our cars, in our living rooms, and in our pockets—and have changed the world beyond our wildest imagination. Yet these marvellous devices are, at the core, amazingly simple and stupid: all they can do is to mechanically shuffle zeros and ones around. What is the true potential of such automated computational devices? And what are the limits of what can be done by mechanical calculations?

Complexity theory gives these deep and fascinating philosophical questions a crisp mathematical meaning. A computational problem is any task that is in principle amenable to being solved by a computer—i.e., it can be solved by mechanical application of mathematical steps. Complexity theory focuses on classifying computational problems according to their inherent difficulty, and on relating those classes of problems to each other. The goal is to understand the power of computers but also—and above all—the limitations of what problems can be solved by them, or more broadly by any type of automated computational process. A problem is regarded as inherently difficult if its solution requires unreasonably large resources regardless of which approach is used to solve it (i.e., no matter which algorithm is employed). Complexity theory formalizes this notion by introducing mathematical models of computation and quantifying the amount of resources needed to solve the problems, such as running time, memory usage, parallelism, communication, et cetera.

This course will give an introduction to computational complexity theory, survey some of the major research results, and present some of the open problems that are the focus of current research. While the intention is to give a fairly broad coverage, there might be a slight bias towards areas where researchers at DIKU have made significant contributions to the state of the art.

Education

MSc Programme in Computer Science
MSc Programme in Physics

Learning outcome

Knowledge of

• Basic concepts in computability and complexity theory and how these concepts are related to one another.
• Foundational research results in modern complexity theory.
• Computational models (e.g., Turing machines, circuits, interactive protocols) and techniques for showing their limitations.
• The power and limits of computability, with a focus on the computationally unsolvable Halting problem.
• Complexity classes such as P, NP, PSPACE, EXPSPACE, L, and NL.
• Tools and techniques for classifying problems according to their computational difficulty (including reductions).
• Computational problems that are computable in principle but appear to be intractable to solve efficiently with theoretical guarantees on algorithm performance.

Skills in

• Using standard tools and techniques in modern complexity theory to solve problems amenable to such methods.
• Presenting foundational results (with proofs and constructions) in writing, using precise terminology and an appropriate level of technical detail.
• Modelling computational problems mathematically and classifying them with respect to computational hardness.

Competences to

• Identify relevant tools and techniques for complexity-theoretic problems.
• Present complexity-theoretic arguments with mathematical stringency orally and in writing.
• Read and understand material on advanced topics in the computational complexity theory research literature.

Lectures and exercise classes.

Most likely, the course will mostly be following the textbook Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, at least for the first half of the course. Towards the end of the course we might use separate lecture notes and/or research articles. More information will be provided on Absalon closer to the start date of the course.

This course is intended to be relevant and accessible to all students, but the main target audience are Master's and PhD students in computer science and mathematics. The course is also suitable for PhD students in mathematics or computer science who have not previously taken a dedicated course on computational complexity theory.

You will need (knowledge equivalent to) basic courses in discrete mathematics and algorithms, and should have a firm grasp of such material. There are no additional formal prerequisites, but you will need mathematical maturity and a willingness to learn new, and sometimes conceptually challenging, material.

Written
Individual
Collective
Continuous feedback during the course of the semester
ECTS
7,5 ECTS
Type of assessment
Continuous assessment
Type of assessment details
4-5 problem sets will be handed out at regular intervals throughout the course. The final grade will be an overall assessment of the results of the problem sets.
Aid
Written aids allowed
Marking scale
Censorship form
No external censorship
Several internal examiners
Re-exam

Students who do not pass on the problem sets will be given the possibility to resubmit assignments and/or to work on and hand in extra problem sets.

##### Criteria for exam assessment

See Learning Outcome.

Single subject courses (day)

• Category
• Hours
• Lectures
• 42
• Preparation
• 116
• Theory exercises
• 16
• Exam
• 32
• English
• 206

### Kursusinformation

Language
English
Course number
NDAA09007U
ECTS
7,5 ECTS
Programme level
Full Degree Master
Duration

1 block

Placement
Block 3
Schedulegroup
A
Capacity
The number of places might be reduced if you register in the late-registration period (BSc and MSc) or as a credit or single subject student.
Studyboard
Study Board of Mathematics and Computer Science
##### Contracting department
• Department of Computer Science
##### Contracting faculty
• Faculty of Science
##### Course Coordinator
• Jakob Nordström   (2-777b4d71763b78823b7178)
##### Teacher

Jakob Nordström
Srikanth Srinivasan
Amir Yehudayoff

Saved on the 14-02-2024

### Are you BA- or KA-student?

Are you bachelor- or kandidat-student, then find the course in the course catalog for students:

Courseinformation of students