Some of the material and ZOOM links (mostly passcode protected) are provided below for each lesson!
Description of the course
The purpose of the course is to study the limits of computation, providing the formal tools and fundamental knowledge to study problems, both tractable and intractable, by a computer. The course is structured in two parts.
In the first part we consider the theory of formal languages and automata, moving from the simplest machines with finite states towards the most powerful Turing Machines and modern computer systems. We explore the limitations of all these systems in the hypothesis of no bound in computing resources such as time or space or energy, hence exploring the nature of problems that admit an algorithmic solution.
The second part considers instead the hierarchy of problems that can be computed within a fixed bound of resources (time and space), the interrelationships among complexity classes, and the study of both NP-complete and provably intractable problems, constituting the theory of computational complexity. The emphasis will be on written problem sets containing challenging problems. The key techniques to be learned are those of simulation of one computational model by another, reduction of one problem to another, and methods for classifying problem complexity.
Grading Scale and Policies
The final grade is based on the percentage of all available points that you receive. A typical example of how percentages might translate into letter grades is A: 91-100, B: 71-90, C: 51-70, D:31-50, E:0-30. Without prior arrangement, missed exams and late homework assignments are not graded for credit. In exceptional circumstances extra time can be requested.
The program is the same for graduate and undergraduate students. Undergraduate students will be assessed using the same scale as graduate students, with the percentage multiplied by a factor of 1.2 for evaluation purposes. Dedicated additional hours will be allocated for clarifications specifically intended for undergraduate students.
Expected schedule in Spring 2024 (Tue & Thu 3:30pm - 4:45pm)
01/11: Course introduction, the main problems in computability and complexity.
Slides 0
01/16: Cantor’s theorem, languages over an alphabet, and the Entscheidungsproblem (the decision problem).
Video HD, Video, Notes, Q&A via ZOOM (passcode protected)
Part 1 (Problems and Computation)
01/18: Regular languages, deterministic finite state automata and non-deterministic ones. The theorems of Rabin-Scott.
Video HD, Video, Notes, Q&A ZOOM (with passcode) ZOOM (without passcode)
01/23: Myhill-Nerode characterisation of regular languages.
Class notes.
01/25: Pumping Lemma for regular languages. Examples of use. Context free languages. (Homework 1)
Video, Class Notes
01/30: Normal forms and Pumping Lemma context free languages.
Video, Class Notes
02/01: Exercises and closure properties of CFL.
Video, Class Notes
02/06: Exercises and Push Down Automata.
Video, Class Notes (with corrected exercise)
02/07: Supplementary material on the relation between Turing Machines and Gödel-Kleene partial Recursive Functions.
Video, Class Notes
02/08: Turing Machines and computable functions. Church-Turing Thesis. Universality of the Turing model of computation.
Video, Class Notes
02/13: s-m-n theorem, compilation and interpretation by Futamura's projections. Non solvable problems.(Homework 2)
Video, Class Notes, Beautiful Video with the Proof
02/15: Recursive and recursive enumerable (re) sets, Post Theorem.
Video, Class Notes
02/20: Kleene theorem of characterisation of re sets. Examples.
Video, Class Notes
02/22: Recursion theorems.
Video, Class Notes
02/27 Rice Theorem and examples.
Video, Class Notes
02/29: Exercises.
Video, Class Notes
03/12: Reduction and completeness (Mid Term exam)
Video, Class Notes
Part 2 (Reduction: Towards Complexity Theory)
03/14: Properties of functional reduction.
Video, Class Notes
03/19: Creative and productive sets. The Computability Hierarchy.
Video, Class Notes
03/20: SI on Gödel Incompleteness.
Video, Class Notes
03/21: Examples (Homework 3)
Video, Class Notes
03/23: Examples and exercises
Video, Class Notes
03/28: Computational complexity and Blum’s abstract theory of computational complexity.
Video, Class Notes
04/02: Properties of computational complexity.
Video, Class Notes
04/04: The Speed-up theorem
Video, Class Notes
04/09: P and NP: properties.
Video, Class Notes
04/11: Reductions and completeness. NP-completeness.
Video, Class Notes
04/16: Examples: SAT and Cook's Theorem.
Video, Class Notes
04/18: Examples.
Video, Class Notes
04/23: Examples, EXP and NEXP. (Homework 4)
04/25: Time hierarchy, Gap Theorem and Ladner’s theorem.
Video, Class Notes
04/30: Space hierarchy, final remarks.
Video, Class Notes
05/08: 3:30-5:30pm Final Exam.
Exam text