|
Home
| Subject Search
| Help
| Symbols Help
| Pre-Reg Help
| Final Exam Schedule
| My Selections
|
Searched for: "18.404" Subjects offered any term 1 subject found.
18.404 Theory of Computation
(
)
(Subject meets with 6.840[J], 18.4041[J])
Prereq: 18.200 or 18.062J
Units: 4-0-8
http://math.mit.edu/classes/18.404
Lecture: TR2.30-4 (2-190) Recitation: F12 (2-139) or F1 (2-139) or F2 (2-139) or F3 (2-139) +final
A more extensive and theoretical treatment of the material in 6.045J/18.400J, 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.
M. Sipser
Textbooks (Fall 2017)
| ||||||||
