University of Siena - Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
The goal of the course is to provide a formal introduction to complexity and computability theory.
The covered topics on computability theory include: universal computational models (single and multi-tape Turing machines, RAM machines, m-recursive functions), Turing decidability and recognisability, reducility, Rice’s theorem, decidability and first order logic, minimum description length. On complexity theory, the introduced topics are: time complexity, P and NP, CoNP, NP-Complete and NP-intermediate, space complexity, probabilistic Turing machines, the polynomial hierarchy. Examples of problems belonging to the introduced computational classes are also given including: decidable/undecidable problems, NP-Complete problems, primality, factorization and graph isomorphism.