Courses:

Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

The syllabus presents the course's objectives, learning outcomes, prerequisites, required readings, format, and policies.

On completion of 6.045, students will be able to explain the basic methods and conclusions of the Theory of Computation. They will be able to apply these methods to problems from different fields and be guided by the results in searching for computational solutions to the problems.

In particular, students will be able to:

1. Explain the theoretical limits on computational solutions of undecidable and inherently complex problems.
2. Describe concrete examples of computationally undecidable or inherently infeasible problems from different fields.
3. Devise and analyze the complexity of procedures to determine properties of computationally bounded automata.
4. Understand formal definitions of machine models.
5. Prove the undecidability or complexity of a variety of problems.

Students will be able to:

1. Synthesize finite automata with specific properties.
2. Convert among multiple representations of finite automata.
3. Use pigeon-holing arguments and closure properties to prove particular problems cannot be solved by finite automata.
4. Calculate asymptotic estimates of the computational complexity of simple procedures from automata, language and graph theory.
5. Prove undecidability using diagonalization and reducibility methods.
6. Use the relationship between recognizability and decidability to determine decidability properties of problems.
7. Describe concrete examples of undecidable problems from different fields.
8. Define, and explain the significance of, the "P = NP?" question and NP-completeness.
9. Describe concrete examples of NP-complete problems from different fields.
10. Prove lower bounds on time and space complexity using diagonalization and polynomial time reducibility methods.
11. Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
12. Describe concrete examples of decidable problems that are known to be unsolvable in polynomial time.

• Undecidability and complexity: 5, 6, 7, 8, 9, 10, 11, 12
• Example undecidable/complex problems: 6, 9, 11, 12
• Automata: 1, 2, 3
• Formal models: 1, 2, 3
• Prove undecidability/complexity: 3, 4, 5, 6, 7, 8, 10, 11

• Synthesize DFA's: 3, 4
• Regular expressions, etc.: 3, 4
• Nonregularity: 3, 4, 5
• Asymptotic complexity: 5
• Undecidable examples: 1, 2
• Undecidability: 1, 5
• Recognizability: 1, 5
• P and NP: 1, 5
• NP examples: 1, 2
• Undecidability and complexity: 1, 5
• Time-space: 1, 2, 5
• Examples: 1, 2

We assume that you have taken 6.042J, Mathematics for Computer Science. 6.045 is, at heart, a mathematics course, and we assume that you are reasonably facile with mathematical concepts. In particular, we assume that you are comfortable with formal mathematical proofs, and can write them up properly.

The book for this class is: Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.

Apart from the textbook, students in the past have found the following books useful. We hope that students who find the textbook unenlightening can consult these books for a different explanation:

• Martin, John. Introduction to Languages and the Theory of Computation. New York, NY: McGraw Hill, 2002. ISBN: 0072322004.
• Kozen, Dexter. Automata and Computability. New York, NY: Springer-Verlag, 1999. ISBN: 0387949070.
• Garey, Michael, and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W.H. Freeman and Company, 1979. ISBN: 0716710455.

There will be (approximately) weekly homework assignments, three in-class quizzes, and a final exam. The final grade will be computed using the following weights:

Homework will be due approximately every week, at the beginning of lecture. We feel it is very important that you turn in the homework assignments on time and we are unable to accept late homeworks. However, when computing your grade at the end of the course, we will drop your lowest homework score. Therefore you need not worry about getting a bad grade on a single assignment.

With regards to homeworks: full credit will be given for correct answers and proofs. We will also grant partial credit for partial solutions and solutions with minor flaws. We will also give a small amount of partial credit for answers which read in full, "I don't know." Likewise, proofs with gaps will receive partial credit, and the partial credit granted will increase if the gaps are explicitly noted. We will give no credit for wildly incorrect answers which are obviously only there in the hopes of getting partial credit. Please only write down answers in which you are confident. Wild guesses only waste our time. Making yourself believe a false proof is bad for your brain.

We require that all homework solutions be typed up. We will provide LaTeX shells for you to flesh out with your solutions, but you do not need to use them. Hand-drawn diagrams are permitted.

We strongly encourage collaboration. We do not expect you to be able to solve every homework problem on your own. We do, however, expect you to write up your own solution to every problem even if the solution is the result of a collaborative effort. To repeat: each person must write up his/her solutions separately. Also, in your write-up please credit the people with whom you worked. If you consult any reference material other than the textbook, please note on your homework which sources you used for each problem.

There will be three quizzes and one final exam. The quizzes will be held during class time on:

• Day 10
• Day 22
• Day 33

Each quiz will cover a unit of the course; the final exam will be cumulative. There will be no homework due on a day on which a quiz is given.