When we define neatly and consider the set of "algorithms" (Turing machines) and the set of "things an algorithm may compute" (functions), we can notice, thanks to an argument from the 19th century (Cantor's diagonal), that there are strictly more "things to compute" than "algorithms to compute them". Then what are these things a computer cannot compute?
This course will teach the basics of computational complexity and answer to the following questions: within the set of computable things, how to define the hardness of a "thing to compute" (aka problem)? When defined neatly (again some maths), these questions raise fundamental open problems of our century, such as the famous 1,000,000 usd question mark: does P equal NP?
You will also be given the tools to say: "this problem is reasonably solvable on a computer" (in P) or "this one is not" (NP-hard).