Computability and complexity [INFOM113]

Learning outcomes

This course aims at providing an introduction to the theories of computability and complexity in computer science.

Objectives

This course aims at providing an introduction to the theories of computability and complexity in computer science.

Content

In a first part we study the basic concepts underlying the theory of computability such as the notion of algorithm, countable sets, computable functions, (semi-)decidable sets and intractable problems. In a second part, we study computational models such as programming languages, lambda-caclculus, recursive functions and Turing machines, and we discuss some key results of computability: the halting problem, Rice's theorem, the relationship between interpretation and compilation and the Futamura projections. In a third section, we introduce the theory of complexity and we study the complexity classes P, NP and coNP. We introduce the class of NP-complete problems and discuss their relevance.