|
Home
| Subject Search
| Help
| Symbols Help
| Pre-Reg Help
| Final Exam Schedule
| My Selections
|
Searched for: 1 subject found.
6.1400[J] Computability and Complexity Theory
(
)
(Same subject as 18.400[J])
Prereq: (6.1200 and 6.1210) or permission of instructor
Units: 4-0-8
Lecture: TR2.30-4 (37-212) Recitation: F11 (4-257) or F1 (24-121) +final
Mathematical introduction to the theory of computing. Rigorously explores what kinds of tasks can be efficiently solved with computers by way of finite automata, circuits, Turing machines, and communication complexity, introducing students to some major open problems in mathematics. Builds skills in classifying computational tasks in terms of their difficulty. Discusses other fundamental issues in computing, including the Halting Problem, the Church-Turing Thesis, the P versus NP problem, and the power of randomness.
R. Williams
Textbooks (Spring 2025)
| ||||||||
