18 400J - Automata, Computability, and Complexity

Institution:

Massachusetts Institute of Technology

Subject:

Description:

Provides an introduction to some of the central ideas of theoretical computer science, including circuits and decision trees, finite automata, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography and one-way functions, computational learning theory, and quantum computing. Examines the classes of problems that can and cannot be solved in various computational models.

Credits:

4.00

Credit Hours:

Prerequisites:

Prereq: 6.042

Corequisites:

Exclusions:

Level:

Instructional Type:

Lecture

Notes:

Additional Information:

Historical Version(s):

Institution Website:

web.mit.edu/student/

Phone Number:

(617) 253-1000

Regional Accreditation:

New England Association of Schools and Colleges

Calendar System:

Four-one-four plan

The Course Profile information is provided and updated by third parties including the respective institutions. While the institutions are able to update their information at any time, the information is not independently validated, and no party associated with this website can accept responsibility for its accuracy.