|
Home
| Subject Search
| Help
| Symbols Help
| Pre-Reg Help
| Final Exam Schedule
| My Selections
|
Searched for: "6.045" Subjects offered any term 1 subject found.
6.045[J] Automata, Computability, and Complexity
(
)
(Same subject as 18.400[J])
Prereq: 6.042
Units: 4-0-8
Mathematical introduction to questions concerning the definition of computation, and what problems can be solved by computers. Considers what problems can be efficiently solved by way of finite automata, circuits, Turing machines, and communication complexity. Provides complete, rigorous answers to the questions in some cases; others are major open problems. Builds skills in classifying computational problems in terms of their difficulty. Discusses other fundamental issues, including the Church-Turing Thesis, the P versus NP problem, and the power of randomness.
Staff
| ||||||||
