# 6.045/18.400Automata, Computability, and Complexity

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

## Objectives

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.

## Learning Outcomes

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.

## Objectives vs Outcomes

### Objectives: related Outcomes

• 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

### Outcomes: reflected Objectives

• Synthesize DFA's: 3, 4
• Regular expressions, etc.: 3, 4
• Nonregularity: 3, 4, 5
• Assymptotic 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