MA 526 Foundations of computation and computational complexity
The goal of this course is to formalize and analyze algorithms in a mathematically rigorous fashion. The course begins with Turing machines (the standard model of computation) and uses them to answer some fundamental questions in computer science and mathematics:, e.g., mathematical truth is undecidable. After that notions offeasibility are introduced and studied, culminating with the famous P vs NP question. Finally there is an introduction to quantum computation.
Distribution
Pure and Applied Mathematics Program