6.1400J/18.400J Computability and Complexity Theory
Repeats every week every Tuesday and every Thursday until Tue May 13 2025 except Tue Feb 18 2025, Tue Mar 25 2025, Thu Mar 27 2025.
Tue, 02/04/2025 - 2:30pm to 4:00pmLocation:
34-304
Instructor:
Ryan Williams
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.