Theory of Computation, Fall 2002
(Complete Item Description)
- Abstract:
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.
- Subject:
- Mathematics and Statistics, Science and Technology
- Grade Level:
- Post-secondary
- Collection:
- MIT OpenCourseWare
