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 daytoday 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
Algorithms and
Complexity Section
at DIKU has made significant contributions to the state of the art.
This course
is
given in the first half of the spring semester (block 3) of 2023.
It
has
a total of 20 lectures, with 2.5 lectures per week on average.
In accordance with the
academic
quarter
tradition,
all times are stated cum tempore,
so
10 am
in the schedule below
actually means 10:15 am et cetera.
Auditorium 06 is located Universitetsparken 5 (HCØ),
and
Auditorium A is at Universitetsparken 15B.
Chapter numbers in the course planning below refer to the
AroraBarak textbook.
The general idea behind the course
is
to first go over (most of) the first 9 chapters in the
textbook,
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
is
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).
Weekday 
Date 
Time 
Room 
# 
Plan of lectures 
References 
Tuesday 
Feb 7 
1012 
Aud A 
1. 
Intro to complexity theory, course overview, Turing machines, undecidability 
Chs 01, notes 
Thursday 
Feb 9 
1315 
Aud 06 
2. 
Complexity classes, reductions, P, NP, nondeterministic computation 
Chs 12, notes 
Tuesday 
Feb 14 
1012 
Aud A 
3. 
NPcompleteness, CookLevin theorem, decision vs. search 
Ch 2, notes 
Thursday 
Feb 16 
1012 
Aud A 
4. 
NPreductions, coNP, EXP, NEXP 
Ch 2, notes 
Thursday 
Feb 16 
1315 
Aud 06 
5. 
Diagonalization, time hierarchy theorems, Ladner's theorem 
Ch 3, notes 
Tuesday 
Feb 21 
1012 
Aud A 
6. 
Oracle TMs, limits of diagonalization, space complexity 
Chs 34, notes 
Thursday 
Feb 23 
1012 
Aud A 
7. 
PSPACE, NPSPACE, PSPACEcompleteness 
Chs 34, notes 
Thursday 
Feb 23 
1315 
Aud 06 
8. 
Savitch's theorem, L, NL, ImmermanSzelepcsényi theorem 
Ch 4, notes 
Tuesday 
Feb 28 
1012 
Aud A 
9. 
ImmermanSzelepcsényi theorem (cont.) 
Chs 45, notes 
Thursday 
Mar 2 
1012 
Aud A 
10. 
Polynomial hierarchy (PH), Boolean circuits, P/poly 
Chs 56, notes 
Thursday 
Mar 2 
1315 
Aud 06 
11. 
KarpLipton theorem, Meyer's theorem, Shannon's lower bound 
Ch 6, notes 
Tuesday 
Mar 7 
1012 
Aud A 
12. 
NC, AC, parallel algorithms, Pcompleteness; randomized computation, BPP 
Chs 67, notes 
Thursday 
Mar 9 
1012 
Aud A 
13. 
Polynomial identity testing, RP, coRP, ZPP, randomized reductions 
Ch 7, notes 
Thursday 
Mar 9 
1315 
Aud 06 
14. 
Interactive proofs, IP, IP=PSPACE (but proof of coNP ⊆ IP) 
Ch 8, notes 
Tuesday 
Mar 14 
1012 
Zoom 
15. 
coNP ⊆ IP (cont.), MIP, PCP 
Chs 89, notes 
Thursday 
Mar 16 
1315 
Zoom 
16. 
Monotone circuits, clique lower bound 
Ch 14, notes 
Tuesday 
Mar 21 
810 
Zoom 
17. 
Clique lower bound for monotone circuits (cont.) 
Ch 14,
notes 
Thursday 
Mar 23 
1517 
Zoom 
18. 
Proof complexity, resolution, interpolation, cliquecolouring lower bound 
[Pud97],
scribe notes 
Tuesday 
Mar 28 
810 
Zoom 
19. 
Cliquecolouring lower bound for resolution (cont.) 
[Pud97],
notes 
Thursday 
Mar 30 
1517 
Zoom 
20. 
Pigeonhole principle lower bound for resolution 
[Hak85],
[Pud00],
scribe notes,
notes

The main instructor on the course is
Jakob Nordström,
who is responsible for all aspects of the course.
Shuo Pang
will be coinstructor, 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 make use of the following
articles:

[Hak85]
Armin Haken:
The Intractability of Resolution.
Theoretical Computer Science,
volume 39, pages 297–308, 1985.

[Pud97]
Pavel Pudlák:
Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.
Journal of Symbolic Logic,
volume 62, issue 3, pages 981–998, 1997.

[Pud00]
Pavel Pudlák:
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
specific area.
Problem Sets
There will be 4 problem sets on this course.
It is compulsory to pass all problem sets to be able to take the
exam.
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
via Absalon
as a PDF file.
State your name and email address
close to the top of the first page.
Solutions should be written in LaTeX or some other mathaware
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.
