18.404J / 6.840J Theory of Computation, Fall 2002
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, comple...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Learning Object |
| Language: | en-US |
| Published: |
2002
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/39661 |
| Summary: | 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. |
|---|