Computability and Complexity (CoCo) 2023
This webpage provides all documentation and information
about the course. There is no additional information in the
Absalon system, but day-to-day messages about the course
and problem set submissions are dealt with there.
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 will probably be a
slight bias towards areas where the
at DIKU has made significant contributions to the state of the art.
given in the first half of the spring semester (block 3) of 2023.
a total of 20 lectures, with 2.5 lectures per week on average.
In accordance with the
all times are stated cum tempore,
in the schedule below
actually means 10:15 am et cetera.
Auditorium 06 is located Universitetsparken 5 (HCØ),
Auditorium A is at Universitetsparken 15B.
Chapter numbers in the course planning below refer to the
The general idea behind the course
to first go over (most of) the first 9 chapters in the
getting a fairly good general overview of computational complexity theory,
and then spend roughly the last third of the course on a selection of more "advanced" topics,
where the textbook
followed less closely.
Please note that the information below about what will be covered in
future lectures is a bit tentative, since the planning might be
slightly revised as we go along
(especially since this is the first time this kind of modern
complexity theory course is given at the University of Copenhagen).
||Plan of lectures
||Intro to complexity theory, course overview, Turing machines, undecidability
||Chs 0-1, notes
||Complexity classes, reductions, P, NP, nondeterministic computation
||Chs 1-2, notes
||NP-completeness, Cook-Levin theorem, decision vs. search
||Ch 2, notes
||NP>-reductions, coNP, EXP, NEXP
||Ch 2, notes
||Diagonalization, time hierarchy theorems, Ladner's theorem
||Ch 3, notes
||Oracle TMs, limits of diagonalization, space complexity
||Chs 3-4, notes
||PSPACE, NPSPACE, PSPACE-completeness
||Chs 3-4, notes
||Savitch's theorem, L, NL, Immerman-Szelepcsényi theorem
||Ch 4, notes
||Immerman-Szelepcsényi theorem (cont.)
||Chs 4-5, notes
||Polynomial hierarchy (PH), Boolean circuits, P/poly
||Chs 5-6, notes
||Karp-Lipton theorem, Meyer's theorem, Shannon's lower bound
||Ch 6, notes
||NC, AC, parallel algorithms, P-completeness; randomized computation, BPP
||Chs 6-7, notes
||Polynomial identity testing, RP, coRP, ZPP, randomized reductions
||Ch 7, notes
||Interactive proofs, IP, IP=PSPACE (but proof of coNP ⊆ IP)
||Ch 8, notes
||coNP ⊆ IP (cont.), MIP, PCP
||Chs 8-9, notes
||Monotone circuits, clique lower bound
||Ch 14, notes
||Clique lower bound for monotone circuits (cont.)
||Proof complexity, resolution, interpolation, clique-colouring lower bound
||Clique-colouring lower bound for resolution (cont.)
||Pigeonhole principle lower bound for resolution
The main instructor on the course is
who is responsible for all aspects of the course.
will be co-instructor, helping out with grading of problem sets,
providing feedback and answering questions,
and giving a few lectures.
We will mostly be following the book
except for towards the end of the course.
In a course like this, the intention is that some lectures will be partly
based on research articles.
In this installment of the course, we will talk about the following
The Intractability of Resolution.
Theoretical Computer Science,
volume 39, pages 297–308, 1985.
Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.
Journal of Symbolic Logic,
volume 62, issue 3, pages 981–998, 1997.
Proofs as Games.
The American Mathematical Monthly,
volume 107, number 6, pages 541–550, 2000.
The lectures will cover the material in the articles
that we need, so students are not required to read
these papers—the references are provided for completeness and for
students interested in further reading. However, for students interested in
learning more, it should be noted that many of the proofs given in
class are actually not those found in the papers, and
more recent survey papers of an area are likely to be better reads
than the original research articles. Please do not hesitate to contact
the instructor if you are interested in specific references for some
There will be 4 problem sets on this course.
It is compulsory to pass all problem sets to be able to take the
Problem sets will be posted on Absalon and below as the
course proceeds, at least one week before the submission deadline.
Problem set 1
(last updated on February 19, 2023): Deadline Tuesday February 21.
Problem set 2
(last updated on February 19, 2023): Deadline Tuesday March 7.
Problem set 3
(last updated on March 19, 2023): Deadline Tuesday March 28.
Problem set 4
(last updated on March 28, 2023): Deadline Monday April 3.
Problem Set Instructions
The following instructions apply for all problem sets.
Please submit your solutions
as a PDF file.
State your name and e-mail address
close to the top of the first page.
Solutions should be written in LaTeX or some other math-aware
typesetting system with reasonable margins on all sides (at least 2.5 cm).
Please try to be precise and to the point in your solutions and
refrain from vague statements. Make sure to explain your reasoning.
Write so that a fellow student of yours can read, understand, and
verify your solutions.
Submissions must be done on time. Blank submissions are not
acceptable and imply an automatic failure on the course. Note,
however, that the submission deadline only specifies the date, and
not the time zone. You are free to submit according to whatever
time zone on earth you like, as long as the date in that time zone is correct.
The intention from the instructor side is to grade and return
submissions after a week.
The threshold for grading is stated on the first page of the
problem set, and any adjustment of this threshold will be
communicated on Absalon. (The threshold can only be adjusted
downwards and never upwards.)
Students who do not pass a problem set can make a
resubmission. Note that you can only resubmit solutions to
problems on the problem set that you actually worked on
before. That is, a resubmission can revise and correct a
previously submitted solution for a problem, but cannot compensate
for an initial blank submission for this problem.
The resubmission deadline is one week after the students have
received their graded problem sets back. This date will be
communicated clearly for each pset.
It is a requirement to pass all problem sets to be allowed to sit
the exam. Students who fail a resubmission, or do a blank
submission will need special permission from the main instructor
on the course to be allowed to take the exam. Of course, there are
all kinds of personal circumstances, and at the end of the day we
want all of you to pass the course. But just bad planning will not
be a sufficient condition to get a waiver. If you would need a
time extension due to special circumstances, do make sure to
contact the main instructor well in advance to check whether these
circumstances are sufficient.
No copying of text, code, or similar is allowed. Although you are
encouraged to discuss with other students, you have to write your
own solution from scratch, and understand all details of it fully.