Computability and Complexity Theory

4-0-8 units · Undergraduate

See description under subject 6.1400J.

Spring 2011 · Automata, Computability, and Complexity

Topics

Introduction
Logic, circuits, and gates
Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs)
NFAs and regular expressions
Non-regular languages and the pumping lemma
Turing machines
Decidability
Undecidable problems and Post correspondence problem (PCP)
Mapping reducibility and Rice’s theorem
Self-reference and the recursion theorem
Introduction to cryptography
Complexity theory
Pseudorandom generators and one-way functions
Public-key cryptography
More complexity theory
More NP-completeness
Probabilistic Turing machines and complexity classes
Trapdoor one-way functions and zero-knowledge proofs
Probably approximately correct (PAC) learning
More PAC learning
Introduction to quantum
Quantum mechanics and BQP
Quantum algorithms

There is no required textbook for the course. However, there are three recommended books:
Listed reading
Moore, Cristopher, and Stephan Mertens. The Nature of Computation . Oxford University Press, 2011. ISBN: 9780199233212.
Listed reading
Sipser, Michael. Introduction to the Theory of Computation . Course Technology, 2005. ISBN: 9780534950972. Covers most material from the first half of the course.
Listed reading
Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach . Cambridge University Press, 2009. ISBN: 9780521424264. Covers most material from the second half (as well as more advanced material that won’t be covered in this course). ↗
Listed reading

Same subject as 6.1400J Prereq: ( 6.1200[J] and 6.1210 ) or permission of instructor U (Spring) 4-0-8 units

Sources

Course catalogue ↗2026–2027
MIT OpenCourseWare ↗Spring 2011
MIT OCW calendar ↗
MIT OCW syllabus ↗
Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.