You are here

Computability and Complexity, Spring 2014

Computability and Complexity (320352)

Jacobs University Bremen, Spring 2014, Herbert Jaeger

Class sessions: Thu + Fri, 14:15 - 15:30, Lecture Hall Res. III

Course description. This lecture presents one half of the core material of theoretical computer science (the other half is covered in the lecture "Formal Languages and Logic''). The question: "What problems can a computer possibly solve?'', is fully answered (by characterizing those solvable problems, equivalently, through Turing machines, random access machines, recursive functions and lambda calculus). A full answer to the related question, "how much computational resources are needed for solving a given problem'' is not known today. However, the basic outlines of today's theory of computational complexity will be presented up to the most famous open problem in computer science, namely the famous "P = NP'' question: if a computer can guess the answer to a problem (and only needs to check its correctness), does that really help to speed up computation?

Course culture. Class presence is mandatory. I will reserve much time to classroom interaction, by asking simple, advanced or outlandish questions, going through miniexercises etc. Like in FLL, students are requested to pre-read in the lecture notes the material that will be covered in class. 10% of the final grade will be based on classroom participation. A good way to reliably score high in this respect is to think of classroom questions while you are doing the pre-reading. Questions can be just mere requests for clarification of the technical contents of the reading, but also probing deep, be about the context of the taught material, challenging me, bewildering classmates. The more we get seriously challenged, the better the question. -- All of this will be started in the second semester week (first week: I'll take the lead with introductory lecturing, no pre-reading).

Homeworks. Students can work in singles or as teams of two but not larger. HW sheets count 1 % of the course score if all problems have been worked on. Correctness of solutions is not required for full scores. It is permissible (though unwise) to copy solutions from friends or other sources.  In this case, the fact that the solutions are copied, as well as the source, must be stated on the HW sheet. TA's will annotate HW sheets that are original work (not copied) to provide useful feedback. If a student copies the solutions and does not indicate that fact and the source, it will be treated as a cheating case (nulling the sheet, notification of the Office of Academic Affairs).

Lecture Notes are here. (latest revision Mar 12, with example of combinatorial completeness added)

For exam preparation, previous finals with solutions from years 2004, 2006, 2008 are here. An exam in the multiple-choice format from 2010 is here in two versions: without solutions and with solutions (you might want to test yourself first on the version without solutions)

Schedule (will be filled in sync with reality as the semester unfolds)


Feb 6 Introduction
Feb 7 Turing Machines (LN Section 3 up to (excluding) Def. 3.2)  Exercise sheet 1
Feb 13 TMs continued. Reading: LN Section 3 up to (including) Definition 3.5 (multitape TMs).
Feb 14 Multi-tape TMs and time complexity. Simulation of 2-tape TM in 1-tape TM. Reading: LN up to (including) Def. 3.8.   Exercise sheet 2
Feb 20 Linear speedup (Prop. 3.5, we skip the rest from Section 3). Random access machines. Reading: Proposition 3.5, Section 4
Feb 21 Miniquiz 1Exercise sheet 3 (new due date)
Feb 27 Primitive recursive functions. Reading: Section 5 up to (including) Example 5.1 .
Feb 28 Mu-recursion, Church's hypothesis,  and universal TMs. Reading: Section 5 to end and Section 6.1.
Mar 6 The halting problem and some of its consequences. Reading: Section 6.2
Mar 7 Undecidability of FOL. Because this is such a fundamental result, the reading is kept to these mere 2 pages. Please make sure that you either understand that proof, or know what questions to ask for clarification. Reading: Section 6.4   Exercise sheet 4
Mar 13 First steps into the world of combinators. Reading: Section 7.1 until (including) Definition 7.3 and the example after that definition.
Mar 14 Miniquiz 2. Combinatorial completeness. Reading: Section 7.1 to end.  Exercise sheet 5
Mar 20 Lambda abstraction. Reading: LN Section 7.2.
Mar 21 Basic programming constructs in lambda calculus. Reading: LN Section 7.3 up to (and including) the "elementary arithmetics" part  Exercise sheet 6
Mar 27 Defining functions by recursion. A simple functional programming language. Reading: Section 7 to end.
Mar 28

Two exmple problems: graph reachability and the TSP. Reading: LN Section 8   Exercise sheet 7

Apr 3 Nondeterministic TMs and the class NP. Reading: Section 9 up to (excluding) Def. 9.7
Apr 4 Miniquiz 3.  Polynomial witnesses and the real-world importance of NP.   Exercise sheet 8
Apr 10 (A glimpse on) relationships between complexity classes. Time hierarchies. Reading: LN Section 10 up to (excluding) Savitch's theorem 10.8 (we skip the rest of this Section this year)
Apr 11 A recap of Boolean logic. Reading: Section 11  No exercises! 
Apr 24 Reductions, completeness. Reading: LN Section 12 up to (and excluding) Theorem 12.3.
Apr 25 Cook's theorem: SAT is NP-complete. Reading: LN Section 12, proof of Cook's theorem. Exercise sheet 9-and-10
May 2 Miniquiz 4  Wrapping up NP-completeness.
May 8 A primer and overview of machine learing, part 1
May 9 A primer and overview of machine learing, part 2  Set of slides of an introduction to machine learning (I used some of these slides in class)
May 15 Tutorial  for exam preparation. And: course evaluation session. Bring your compters!
May 16 Tutorial, continued.
May 22

16:00 hrs: final exam  (East Wing, Campus Center)


  • Papadimitriou, C: Computational Complexity, (Addison-Wesley) IRC: QA267.7 .P36 1994
  • Hopcroft, John E. , Motwani, Rajeev, and Ullman, Jeffrey: Introduction to Automata Theory, 2nd (Addison-Wesley) IRC: QA267 .H56 2001
  • Garey, Michael and Johnson, David: Computers and Intractability: A guide to the Theory of NP-completeness (Macmillan) IRC: QA76.6 .G35

Grading and exams: Grading and exams: The final course grade will be composed from homeworks (10%), presence sheets (10%), active participation in class (5%), and quizzes/exams. There will be four miniquizzes (written in class, 20 minutes), the best three of which will each account to 15% of the final grade (worst will be dropped from calculating the grade), and one final exam, counting 30%. All quizzes are open book. Each quiz or exam yields a maximum of 100 points. The total semester points Pts_total are computed as the weighted semester point average (each quiz points are weighted by 0.15, the final by 0.30, etc.), and from Pts_total the final grade is computed by the standard Jacobs formula.

Miniquiz makeup rules: if a miniquiz is missed without excuse, it will be graded with 0 points. An oral makeup will be offered for medically excused miniquizzes according to the Jacobs rules (especially, the medical excuse must be announced to me on the day of the miniquiz). Non-medical excuses can be accepted and miniquiz makeups be arranged on a case-by-case basis.