# Computability and Complexity, Spring 2019

#### Jacobs University Bremen, Spring 2019, Herbert Jaeger

**Class sessions:**** **

Tuesdays 11:15 – 12:30 (Lecture Hall Res. 1)

Fridays 14:15 – 15:30 (East 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
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:** The final course grade will be composed from homeworks (15%), presence sheets (10%), and quizzes (45%) and a final exam (30%). There will be three miniquizzes (written in class, 30 minutes), the best two of which will be counted (worst will be dropped). 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. One makeup will be offered soon after the quiz for
medically excused miniquizzes according to the Jacobs rules (especially,
the medical excuse must be announced to me *before* the quiz).
Non-medical excuses can be accepted and makeups be arranged on a
case-by-case basis. If the first makeup is likewise missed for medical reasons, similar rules apply to get admitted to a second makeup (medical excuse must be announced to me before the makeup). The second makeup is then to sit for the quiz in the next year’s edition of this course; or the student may opt to get the grade of the final exam counted also as grade for the quiz.

**Lecture Notes** are here (last revision March 21, several minor readability improvements)

**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**: Mihail Tarigradschi (m.tarigradschi at jacobs-university.de) and Mohit Shrestha (mo.shrestha 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 5 | Introduction |

Feb 8 | Equivalence of computing functions, deciding languages, and solving problems. Definition of Turing machines. Recursive languages and functions, recursively enumerable languages. Reading: LN Sections 3.1, 3.2. Exercise sheet 1 Solutions to sheet 1 |

Feb 12 | Busy Beavers. TMs with multiple tapes. Time classes. Reading: LN Sections 3.3, 3.4 up to (excluding) Proposition. 3.2. |

Feb 15 | Simulating multiple tapes in a single tape. Reading: LN Section 3.4 (complete) Exercise sheet 2 | Solutions |

Feb 19 | Random Access Machines. Reading: LN Section 4. |

Feb 22 | Primitive recursive functions. Reading: LN Section 5 up to (including) Example 5.1 Exercise sheet 3 | Solutions |

Feb 26 | Miniquiz 1 Recursive functions. Church-Turing Hypothesis. No reading |

Mar 1 | Universal TMs. The halting problem. Reading: LN Section 6.1, 6.2 up to (including) Proposition 6.2 Exercise sheet 4 | Solution |

Mar 5 | Undecidability results by reduction. Rice's theorem. Reading: LN Section 6.2, complete |

Mar 8 | Undecidability of FOL. Reading: LN Section 6.4 (we skip 6.3) Exercise sheet 5 | Solution |

Mar 12 | Combinators: intro. No reading. |

Mar 15 | no class |

Mar 19 | Grammar of combinatorial terms. S, K, I combinators. Reductions. Evaluation order. Combinatorial completeness. Reading: Section 7.1 |

Mar 22 | The lambda operator. Reductions with lambda-terms. Reading: LN Section 7.2 Exercise sheet 6 | Solution |

Mar 26 | Miniquiz 2 (in class) Basic programming
constructs in lambda calculus: intro. Booleans. No reading. |

Mar 29 | Basic programming constructs in lambda calculus. Integer
arithmetics. Reading: LN Section 7.3 Exercise sheet 7 | Solution |

Apr 2 | Recursion and the Y combinator. Streams. Reading: Section 7.3, 7.4 |

Apr 5 | A simple - but Turing-complete - functional programming language. Reading: Section 7.5 Exercise sheet 8 | Solution |

Apr 9 | Part II: Complexity. Two quite different problems: Graph reachability and the Traveling Salesman Problem. Polynomial vs. exponential time complexity. Reading: LN Sections 8.1-8.3 |

Apr 12 | Nondeterministic TMs and the class NP. Reading: LN Section 9 up to (including) Def. 9.5 Exercise sheet 9 |

Apr 23 | Characterizing NP by polynomially decidable and balanced relation. The P =? NP question. Reading: LN Section 9 to end |

Apr 26 | Some standard complexity classes. Hierarchy theorems. Reading: LN Section 10. (No exercises this week) |

Apr 30 | |

May 3 | |

May 7 | |

May 10 | |

May 14 | |

May 20 | 16:00-18:00, SSC Hall 3: Final Exam |