Theory of Computation, Fall 2002

View Resource

Remix and Share

Author:

Sipser, Michael

Subject:

Mathematics and Statistics, Science and Technology

Institution Name:

M.I.T.

Collection:

MIT OpenCourseWare

Grade Level:

Post-secondary

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.

Languages:

English

Material Type:

Assessments, Full Course, Homework and Assignments, Syllabi

Media Format:

Text/HTML, Downloadable docs

Conditions of Use:

Creative Commons Attribution-Noncommercial-Share Alike 3.0