|
Home
| Subject Search
| Help
| Symbols Help
| Pre-Reg Help
| Final Exam Schedule
| My Selections
|
Searched for: 1 subject found.
6.840[J] Theory of Computation
(
)
(Same subject as 18.4041[J])
(Subject meets with 18.404)
Prereq: 6.042 or 18.200
Units: 4-0-8
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. Students in Course 18 must register for the undergraduate version, 18.404.
M. Sipser
| ||||||||
