Theoretical Computer Science

The course introduces basics of computability and complexity theory, presenting suitable theoretical tools which also turn out to be useful to rigorously approach several other issues in computer science. The notion of algorithmically solvable problem is formally characterized, as well as the class of unsolvable problems analyzed. Next, problems are investigated, on the basis of computational resource requirements for algorithmic solution, rigorously defining the notion of algorithmic efficiency. In this realm, the celebrated P = NP question is tackled.

The student will acquire tools and techniques in computability and complexity theory, which are fundamental in any research investigation in computer science and, more generally, in the rigorous analysis of problems and their algorithmic solutions. She/he will be able first to correctly state and model problems, and then formally investigate algorithmic solutions from several viewpoints.