# 6.045/18.400Automata, Computability, and Complexity

 Course Home Page General Information/Policies Contact Info Objectives and Outcomes Calendar Course Materials by Lecture Date

## Finite Automata, Regular Languages, Regular Expressions

### Lecture 2 (Mon Feb 09): Deterministic Finite Automata

• Deterministic Finite Automata (DFA) and the languages they accept.

### Lecture 3 (Wed Feb 11): Nondeterministic Finite Automata

• Nondeterministic Finite Automata (NFA) and the languages they accept.
• Homework 1 due. (Solutions)
• Homework 2 out (LaTeX source); will be due on Wednesday Feb 18.

### Lecture 4 (Tue Feb 17): Regular Expressions

• Regular Expressions describe Regular Languages

### Lecture 6 (Mon Feb 23): Algorithms for Automata

• Reading: Chapter 1, Section 4.1

### Lecture 7 (Wed Feb 25): Quiz 1

• Quiz 1, in class: open book (see handout 2 above for details).
• Check out the Quiz 1 Solutions.
• Material covered: Lectures 1 through 6; Chapters 0 and 1.
• Homework 3 out (LaTeX source); will be due on Wednesday, March 3.

### Recitation 4 (Thurs Feb 26): Quiz Questions & Automata Wrap-up

• Return Quiz 1 and answer questions.
• Discuss algorithms for automata.
• Recitation 4: Discussion Materials

## Computability Theory

### Lecture 8 (Mon Mar 01): Turing Machines

• Reading: Chapter 3 (Sections 3.1, 3.3, and 3.2 - except Nondeterminism)
• Introduction to Turing Machines

### Lecture 9 (Wed Mar 03): Nondeterministic Turing Machines

• Reading: Section 3.2 (especially pages 138-141), Section 4.2 (especially pages 160-164)
• Homework 3 due (Solutions).
• Homework 4 out (LaTeX source); will be due on Wednesday, March 10.
• Nondeterministic TMs are no more powerful than regular TMs
• Definition of decidable and enumerable languages
• Counting arguments and Cantor's diagonalization

### Lecture 10 (Mon Mar 08): Undecidability

• Reading: Chapter 4 (skip pages 156-158 on context-free languages), Section 5.1 (up to 176)
• The Halting Problem is Undecidable

### Lecture 11 (Wed Mar 10): PCP

• Reading: Computation histories (see page 176) and Sections 5.2
• Homework 4 due (Solutions).
• Homework 5 out (LaTeX source); will be due on Wednesday, March 17. Here is an extra hint for problem 2; try to think about the problem on your own first.
• The Post Correspondence Problem is Undecidable

### Recitation 6 (Thurs Mar 11): Undecidability

• Reading: Chapter 4 (up to page 176), Sections 5.1 (except 181-182), 5.2
• Practicing with decidability and undecidability
• Recitation 6: Discussion Materials

### Lecture 12 (Mon Mar 15): Reducibility

• Reading: Section 5.3, Handout 6
• Handout 6: A photocopy of Lecture 34 from Kozen on Rice's Theorem will be passed out in class.
• Reductions, Mapping Reducibility, Rice's Theorem

### Lecture 14 (Mon Mar 29): Counter and Stack Machines

• Handout 10: a photocopy of Section 8.5 on counter machines from Hoptcroft, Motwani and Ullman will be passed out in class.
• Other machines and undecidability

### Lecture 15 (Wed Mar 31): Quiz 2

• Quiz 2, in class.
• Check out the Quiz 2 Solutions.
• Material covered: Lectures 8 through 14; Chapters 3, 4, 5 and 6.1 (except context-free material on pages 156-158 and 181-182).
• Homework 6 out (LaTeX source); will be due on Wednesday, April 7.

## Complexity Theory

### Lecture 16 (Mon Apr 05): Time Complexity

• Time Complexity, The Class P

### Lecture 17 (Wed Apr 07): Nondeterministic Time Complexity

• The Class NP, Examples of NP Problems, P vs NP
• Homework 6 due (Solutions).
• Homework 7 out (LaTeX source); will be due on Wednesday, April 14.

### Recitation 9 (Thurs Apr 08): P and NP

• Reading: Sections 7.1, 7.2, 7.3
• Definitions and Examples of P and NP Problems
• Recitation 9: Discussion Materials

### Lecture 18 (Mon Apr 12): NP-Completeness

• Reading: Sections 7.4 (Except Theorem 7.30)
• Polynomial Time Reductions, Definition of NP-Completeness

### Lecture 19 (Wed Apr 14): Cook-Levin Theorem

• Reading: Section 7.4 (Theorem 7.30)
• SAT, 3SAT, and CLIQUE are NP-Complete
• Homework 7 due (Solutions).
• Homework 8 out (LaTeX source); will be due on Wednesday, April 21.

### Lecture 20 (Wed Apr 21): NP-Completeness II

• HAMPATH, SUBSET-SUM, 3-DIM-MATCHING and many more languages are NP-Complete
• WARNING: the polynomial time reduction of 3SAT to HAMPATH is incorrect in OLD versions of Sipser (i.e., the first printing). The problem is that the diamond gadgets are missing separator nodes.
• Homework 8 due (Solutions).
• "Fake" Homework 8.5 out (Solutions); these problems should be used to practice the material covered in lectures 19, 20 and 21; they will not be due.
• Handout 12: Quiz 3 Information and Review Material.
• Handout 13: Sample Quiz 3.
• Handout 14: Sample Quiz 3 Solutions.
• More Practice Problems for Quiz 3. These are extra problems to help you study SOME (but not all) of the material covered on Quiz 3. No solutions will be provided.

### Recitation 11 (Thurs Apr 22): NP-Completeness

• "Harder" polynomial-time reductions, gadgets, and games
• Recitation 11: Discussion Materials

### Lecture 21 (Mon Apr 26): Advanced Time Complexity

• Traveling Salesman Problem: Optimization vs Decision
• The Classes: EXP and NEXP
• Oracle Complexity Classes

### Recitation 12 (Thurs Apr 29): Quiz 3 Questions & End of Time Complexity

• Review Quiz 3 solutions.
• More practice with NP-completeness.
• Recitation 12: Discussion Materials

### Lecture 23 (Mon May 03): Space Complexity

• Reading: Sections 8.4, 8.5, 8.6
• Space-Bounded Computation, The Class L, NL = Co-NL

### Lecture 24 (Wed May 05): Space Complexity II

• Reading: Sections 8.4, 8.5, 8.6
• Homework 9 due (Solutions).
• "Fake" Homework 10 out (Solutions); these problems should be used to practice the material covered in lectures 23, 24, and 25; they will not be due.

### Recitation 13 (Thurs May 06): Space Complexity III

• Reading: Sections 8.4, 8.5, 8.6
• Space Complexity

### Lecture 25 (Mon May 10): Probabilistic Complexity

• The Class BPP