18.404J / 6.840J Theory of Computation, Fall 2002

18.404J / 6.840J Theory of Computation, Fall 2002

Show other versions (1)

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...

Full description

Bibliographic Details
Main Author: Sipser, Michael
Language:en-US
Published: 2002
Subjects:
computability
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
interactive proof systems
18.404J
6.840J
18.404
6.840
Online Access:http://hdl.handle.net/1721.1/39661

Internet

http://hdl.handle.net/1721.1/39661

Similar Items