everything.study
18.404

Theory of Computation

4-0-8 units · Undergraduate

A more extensive and theoretical treatment of the material in 6.1400J/ 18.400[J] , emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.

Fall 2020

Topics

  • Introduction, Finite Automata, Regular Expressions
  • Nondeterminism, Closure Properties, Regular Expressions → Finite Automata
  • The Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs
  • Pushdown Automata, CFG ↔ PDA
  • The CF Pumping Lemma, Turing Machines
  • TM Variants, the Church-Turing Thesis
  • Decision Problems for Automata and Grammars
  • Undecidability
  • Reducibility
  • The Computation History Method
  • The Recursion Theorem and Logic
  • Time Complexity
  • P and NP, SAT, Poly-time Reducibility
  • NP-Completeness
  • Cook-Levin Theorem
  • Space Complexity, PSPACE, Savitch’s Theorem
  • PSPACE-Completeness
  • Games, Generalized Geography
  • L and NL, NL = coNL
  • Hierarchy Theorems
  • Provably Intractable Problems, Oracles
  • Probabilistic Computation, BPP
  • Probabilistic Computation (cont.)
  • Interactive Proof Systems, IP
  • coNP ⊆ IP

Readings

  • Sipser, Michael. Introduction to the Theory of Computation . 3 rd ed. Cengage Learning, 2012. ISBN: 9781133187790.
    Listed reading
  • You may use the second edition, but it is missing some additional practice problems. Errata for 2 nd edition of textbook . ↗
    Listed reading
  • We will cover Chapters 1, 2 (except 2.4), 3, 4, 5, 6.1, 7, 8, 9.1, 9.2, 10.2 (except the part on Primality), and 10.4 through Theorem 10.33.
    Listed reading
  • This course is taught using Professor Sipser’s textbook:
    Listed reading
  • Sipser, Michael. Introduction to the Theory of Computation . 3rd ed. Cengage Learning, 2012. ISBN: 9781133187790.
    Listed reading
  • LEC #: 1 · TOPICS: Introduction, Finite Automata, Regular Expressions · READINGS: Section 1.1
    Reading assignment
  • LEC #: 2 · TOPICS: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata · READINGS: Sections 1.2 and 1.3
    Reading assignment
  • LEC #: 3 · TOPICS: The Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs · READINGS: Sections 1.4, 2.0, and 2.1
    Reading assignment
  • LEC #: 4 · TOPICS: Pushdown Automata, CFG ↔ PDA · READINGS: Section 2.2
    Reading assignment
  • LEC #: 5 · TOPICS: The CF Pumping Lemma, Turing Machines · READINGS: Sections 2.3 and 3.1
    Reading assignment
  • LEC #: 6 · TOPICS: TM Variants, the Church-Turing Thesis · READINGS: Sections 3.2 and 3.3
    Reading assignment
  • LEC #: 7 · TOPICS: Decision Problems for Automata and Grammars · READINGS: Section 4.1
    Reading assignment
  • LEC #: 8 · TOPICS: Undecidability · READINGS: Section 4.2
    Reading assignment
  • LEC #: 9 · TOPICS: Reducibility · READINGS: Section 5.1
    Reading assignment
  • LEC #: 10 · TOPICS: The Computation History Method · READINGS: Section 5.2
    Reading assignment
  • LEC #: 11 · TOPICS: The Recursion Theorem and Logic · READINGS: Sections 6.1 and 6.2
    Reading assignment
  • LEC #: 12 · TOPICS: Time Complexity · READINGS: Section 7.1
    Reading assignment
  • LEC #: 14 · TOPICS: P and NP, SAT, Poly-time Reducibility · READINGS: Sections 7.2 and 7.3
    Reading assignment
  • LEC #: 15 · TOPICS: NP-Completeness · READINGS: Section 7.5
    Reading assignment
  • LEC #: 16 · TOPICS: Cook-Levin Theorem · READINGS: Section 7.4
    Reading assignment
  • LEC #: 17 · TOPICS: Space Complexity, PSPACE, Savitch’s Theorem · READINGS: Sections 8.1 and 8.2
    Reading assignment
  • LEC #: 18 · TOPICS: PSPACE-Completeness · READINGS: Section 8.3
    Reading assignment
  • LEC #: 19 · TOPICS: Games, Generalized Geography · READINGS: Section 8.3
    Reading assignment
  • LEC #: 20 · TOPICS: L and NL, NL = coNL · READINGS: Section 8.4
    Reading assignment
  • LEC #: 21 · TOPICS: Hierarchy Theorems · READINGS: Section 9.1
    Reading assignment
  • LEC #: 22 · TOPICS: Provably Intractable Problems, Oracles · READINGS: Section 9.2
    Reading assignment
  • LEC #: 23 · TOPICS: Probabilistic Computation, BPP · READINGS: Section 10.2
    Reading assignment
  • LEC #: 24 · TOPICS: Probabilistic Computation (cont.) · READINGS: Section 10.2
    Reading assignment
  • LEC #: 25 · TOPICS: Interactive Proof Systems, IP · READINGS: Section 10.4
    Reading assignment
  • LEC #: 26 · TOPICS: coNP ⊆ IP · READINGS: Section 10.4
    Reading assignment

Prerequisites & course information

Subject meets with 6.5400J, 18.4041J Prereq: 6.1200[J] or 18.200 U (Fall) 4-0-8 units

Sources