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).