Computability and Complexity, Spring 2018
Jacobs University Bremen, Spring 2018, Herbert Jaeger
Class sessions:
Thursdays 14:15 – 15:30 (until March 15: East Hall 4; after March 15: East Hall 8)
Fridays 14:15 – 15:30 (West Hall 8)
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 online lecture notes are a fully self-contained, textbook-style, detailed text. All exam questions are based solely on what is in the lecture notes. Thus, a student could perfectly pass this course by just home-studying the lecture notes, tuning his/her skills on the weekly homeworks, sit in the exams, and be done without ever seeing me. Ooops. I do want to see my students… Easy: I make classroom attendance mandatory. Ooops again - mandatory boredom? Solution: (i) mandatory classroom presence, (ii) mandatory pre-reading of the lecture note portion of the day, (iii) in class I will only briefly rehearse the pre-read lecture note material, making sure that everybody has a good grasp of it, and then (iv) I will spend most of the classroom time telling you stuff that is related to the lecture note material, but outside of it – stuff you will not find in typical lecture notes: historical background, applications, connections of computer science to other sciences, tricky problems and open questions, math minitutorials, and more. This “extra” stuff will, I hope, make attendance worth its while, although it is not exam-relevant. You will, I hope very much, be amazed how deeply the technical material of this lecture is connected to realities outside CS.
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 (10%), presence sheets (10%), and quizzes/exams. There will be three miniquizzes (written in class, 30 minutes), the best two of which will each account to 25% of the final grade (worst will be dropped), and one final exam, counting 30%. All quizzes and the final exam are open book.
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 April 5, 2018 – again cleaned up some font conversion hickups, now cleared up to the end of the manuscript)
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: Yu Pan (y.pan at jacobs-university.de) and Temirlan Ulugbek uulu (t.ulugbekuulu at jacobs-university.de)
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 1 |
Introduction |
| Feb 2 | Why Turing invented the Turing Machine (slides). -- Equivalence of computing functions, deciding languages, and solving problems. -- Def. of TM. |
| Feb 8 | Setting up TMs for different kinds of tasks. Recursive and recursively enumerable languages. Busy Beavers. Reading: LN Sections 3.1, 3.2, 3.3 Exercise sheet 1 |
| Feb 9 | Multi-tape TMs. Time classes. Simulating multiple tapes in a single tape. Reading: LN Section 3.4 up to (including) Def. 3.8 |
| Feb 15 | Polynomial relatedness. Tightness of quadratic loss bound. Space complexity. Linear speedup. Reading: LN Section 3 to its end. |
| Feb 16 | Random Access Machines. Reading: LN Section 4. Exercise sheet 2 |
| Feb 22 | Primitive recursive functions. Ackermann function, mu-recursion. Reading: LN Section 5 up to (including) Example 5.1 |
| Feb 23 | Church-Turing hypothesis. A glimpse of cellular automata. Reading: Lecture notes Section 5 (complete) Exercise sheet 3 |
| Mar 1 | Universal TMs. The halting problem. Reading: LN Section 6 up to (including) Prop. 6.2 (and its proof!) |
| Mar 2 | Undecidability results by reduction. Rice's theorem. Reading: LN Section 6 up to (including) 6.2 Exercise sheet 4 |
| Mar 5 | 15:45 first miniquiz - Lecture Hall in Res. 1 |
| Mar 8 | Undecidability of FOL. Reading: LN Section 6.4 (we skip 6.3) Exercise sheet 5 |
| Mar 9 | no class |
| Mar 15 | Combinators: intro. No reading. Exercise sheet 6 |
| Mar 16 | Combinatorial algebras: evaluation order. Combinatorial completeness. Reading: Section 7.1 to end |
| Mar 22 | The lambda operator. Reductions. Reading: LN Section 7.2 Exercise sheet 7 |
| Mar 23 | Basic programming constructs in lambda calculus. Reading: LN Section 7.3 up to (including) the part on "Elementary arithmetics". |
| Apr 5 | Recursion and the Y combinator. Streams. Reading: Section 7.3, 7.4 |
| Apr 6 | Complexity: intro. Reading: LN Section 8 Exercise sheet 8 |
| Apr 10 | 19:00 second miniquiz - Lecture Hall in Res. 1 |
| Apr 12 | Nondeterministic TMs. The class NP. Reading: LN Section 9 up to (excluding) Def 9.7 Exercise sheet 9 |
| Apr 13 | Characterizing NP by polynomially decidable and balanced relation. The P =? NP question. Reading: LN Section 9 to end |
| Apr 19 | The practical importance of NP. Relationships between complexity classes. Hierarchy theorems. A choice of known facts. Reading: LN Section 10 |
| Apr 20 | A recap of propositional logic, and some complexity facts about Boolean inference. Exercise sheet 10 |
| Apr 26 | Reductions and completeness. Reading: LN Section 12.1, 12.2 up to (excluding) Theorem 12.3 |
| Apr 27 | Cook's theorem: SAT is NP-complete. Reading: LN Section 12.2 to end Exercise sheet 11 |
| May 3 | Remaining sessions not documented since website was hacked. |
| May 4 | |
| May 11 | |
| May 26 | Final exam, 12:30 - 14:30, CNLH (pre-announcement, subject to confirmation) |