CS 740: Complexity Theory and Algorithm Analysis

What does it mean to say that some computational problem is intrinsically more difficult than some other problem? How can I claim that I have found a good algorithmic solution? The study of these questions gives rise to an area of Theoretical Computer Science called Complexity Theory, which is based on a systematic and thorough formal study of the complexity of problems with respect to their algorithmic solvability, using Turing machines as main conceptual tool. In this class, we will understand how problem and algorithm complexity is measured, and discuss some of the main complexity classes arising from this study. In particular, we will cover the classes P and NP, and their relationship