You are here

Computability and Complexity, Spring 2017

Computability and Complexity (CO21-320352)

Jacobs University Bremen, Spring 2017, Herbert Jaeger

Class sessions: Thursdays and Fridays 15:45 – 17:00, West Hall 4

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. Like in FLL in Fall, the basic idea is that participants pre-read the daily material, which is then rehearsed in the first part of a classroom session, after which I will reserve time to classroom interaction, by asking simple, advanced or outlandish questions, going through miniexercises, present add-on material, etc. 5% 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. Classroom presence is mandatory.

Homeworks. Students can work in singles or as teams of two but not larger. HWs count 10 % of the course score. Homework sheets are not graded in the usual sense. Instead, a HW sheet gets a full score if all problems have been visibly and convincingly worked on. Correctness of solutions is not required for full score. 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).

Grading and exams: Grading and exams: The final course grade will be composed from homeworks (15%), presence sheets (10%), 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), and one final exam, counting 30%. All quizzes and the final exam are open book. Each quiz or exam yields a maximum of 100 points.

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 makeups be arranged on a case-by-case basis.

Lecture Notes are here (version from Feb 3)

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 (and these are the solutions)

TAs for this course are Hang Yuan and Rubin Deliallisi.

References

  • 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
  • A tutorial text by  on lambda calculus by L. C. Paulson (my lecture notes owe a lot to this tutorial)

Schedule (this will be filled in synchrony with reality as we go along)

Feb 2

       Introduction                
Feb 3 Turing machines: basic definitions.  Lecture notes 3.2  Exercise sheet 1
Feb 9 Recursive and rec. en. languages; recursive and partially rec. functions; busy beavers and the Rado function. Reading: LN Section 3.2 to end, 3.3 (the busy Beaver section)
Feb 10 Multi-tape TMs. Time complexity classes. Mutual simulation complexity of multi- and single-tape TMs. Reading: LN Section 3.4 up to (including) Proposition 3.2  Solutions to exercises 1  Exercise sheet 2
Feb 16 Polynomial relatedness of time complexities. Tightness of quadratic TM simulation bound. Linear speedup. Reading: LN Section 3 to end.
Feb 17 Random access machines. Reading: Section 4 Solutions to exercises 2 Exercise sheet 3
Feb 23 Miniquiz 1  Exercising our wits with almost trivial and with almost or even totally impossible problems.
Feb 24  Primitive recursive functions. No reading Solutions to exercises 3  Exercise sheet 4
Mar 2 Ackermann function, mu-recursion. Church-Turing hypothesis. Reading: Lecture notes Section 5 (complete)
Mar 3 Universal TMs. The halting problem. Reading: LN Section 6 up to (including) Prop. 6.2 (and its proof!) Solutions to exercise sheet 4  Exercise sheet 5
Mar 9 no class
Mar 10 no class
Mar 16 Undecidability results by reduction. Rice's theorem. Reading: LN Section 6 up to (including) 6.2
Mar 17 Miniquiz 2  Undecidability of first order logic. No reading.  Solution to exercise sheet 5   Exercise sheet 6
Mar 23 Combinators: intro. Reading: Section 7.1 up to (including) Def. 7.2 Solution to exercise sheet 6  Exercise sheet 7
Mar 24 Combinatorial algebras: evaluation order. Combinatorial completeness. Reading: Section 7.1 to end
Mar 30 The lambda operator. Reductions. Reading: LN Section 7.2   Solutions to sheet 7 Exercise sheet 8
Mar 31 Basic programming constructs in lambda calculus. Reading: LN Section 7.3 up to (including) the part on "Elementary arithmetics".
Apr 6 Elementary arithmetics in lambda calculus. Recursion and the Y combinator. Streams. Reading: Section 7.3, 7.4 Solutions to sheet 8  Exercise sheet 9
Apr 7 Miniquiz 3  Equivalence of lambda calculus with Turing computability. No reading
Apr 20 Complexity: intro. Reading: LN Section 8
Apr 21 Nondeterministic TMs. The class NP. Reading: LN Section 9 up to (excluding) Def 9.7  solutions to sheet 9  Exercise sheet 10
Apr 27 Characterizing NP by polynomially decidable and balanced relation. The P =? NP question. Reading: LN Section 9 to end
Apr 28 Relationships between complexity classes and hierarchy theorems. Reading: LN Section 10 solutions to sheet 10  Exercise sheet 11
May 4 Miniquiz 4  Boolean logic re-visited under the auspices of computational complexity. No reading
May 5 Reductions and completeness. Reading: LN Section 12.1, 12.2 up to (excluding) Theorem 12.3 Exercise sheet 12
May 11 (Online course evaluation - please bring your laptops or tablets or smartwatches)
May 12  
May 26 Final exam: 9:00 - 11:00, LH Res. III