# NDAA09007U Computability and Complexity (CoCo)

MSc Programme in Computer Science

MSc Programme in Physics

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.

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

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.

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.

- Category
- Hours
- Lectures
- 42
- Preparation
- 116
- Theory exercises
- 16
- Exam
- 32
- Total
- 206

As
an exchange, guest and credit student - click here!

Continuing Education - click here!

*PhD’s can register for MSc-course by following the same
procedure as credit-students, see link above.*

- Credit
- 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
- 7-point grading 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 assesment

See Learning Outcome.

### Course information

- Language
- English
- Course code
- NDAA09007U
- Credit
- 7,5 ECTS
- Level
- Full Degree Master
- Duration
- 1 block
- Placement
- Block 3
- Schedule
- A
- Course 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.

##### Study board

- Study Board of Mathematics and Computer Science

##### Contracting department

- Department of Computer Science

##### Contracting faculty

- Faculty of Science

##### Course Coordinators

- Jakob Nordström (2-6e7244686d326f7932686f)

##### Lecturers

Jakob Nordström

Srikanth Srinivasan

Amir Yehudayoff