Salta ai contenuti. | Salta alla navigazione

Strumenti personali


Academic year and teacher
If you can't find the course description that you're looking for in the above list, please see the following instructions >>
Versione italiana
Academic year
Didactic period
Secondo Semestre

Training objectives

This course introduces the main methodologies for the analysis of the computability and the complexity of a decision problem.

Topics covered (Knowledge):

- introduction to the decision problems and their relationship with functional and optimization problems.
- regular language, Pumping Lemma, existence of non-regular languages, finite state automata
- context-free languages, Pumping Lemma, existence of non-context-free languages, stack automata
- the Turing machine model, and the Church-Turing thesis.
- many one reductions and Turing reductions
- the concept of complexity class
- the classes P and NP, and their relationship
- NP-complete problems
- appriximation to NP-complete problems
- the classes NLOGSPACE, PSPACE, and NPSPACE, and Satvich'a theorem
- other important classes and separation theorems.
- introduction to the relationship between computability and artificial intelligence

At the end of the course, the student will be able to (Abilities):

- recognize a computable decision problem from a non computable one (in simple cases)
- recognize the complexity class of a computable problem (in simple cases)
- understand the mathematics behind a problem and the issues relative to its classification
- understand the role played by some classical problems, in particular logic-based problems


Basic knowledge in logics and programming (any language). Having successfully passed Algorithms and Data Strutures

Course programme

(8 ore): Propositional logic, first-order logic, satisfiability, validity, automatic reasoning models, sub-propositional logigs, super-propositional logics, descriptive complexity.
(4 hours): Church-Turing thesis via alternative models to the Turing machine and their equivalence. Computable decision problems, semi-computable decision problems, and existence of non-computable decision problems.calcolabile.
(4 hours): Many-one and Turing reductions. The classes DEC, RE, and CO-RE, and classical examples of non-computable problems and semi-computable problems. The concept of RE-complete e CO-RE-complete problem.
(4 hours): Satisfiability problem for formulas of the first order logic of natural numbers.
(4 hours): Complexity class definition. P and NP. NP-complete problems.
(4 hours): Classical NP-complete problem and their reductions. Approximations to NP-complete problems.
(3 hours): LOGSPACE, NLOGSPACE, PSPACE e NPSPACE. The concept of transductor. Polynomial reductions. Satvich theorem.
(3 hours): EXPTIME, NEXPTIME, EXPSPACE, NEXPSPACE. Separation theorems.
(2 ore): modern IA and its relationship with complexity and computability theory

Didactic methods

Standard classes. Students may also watch the recorded classes from previous academic years on the professor's YouTube page.

Learning assessment procedures

Oral exam.

Reference texts

*************** ATTENTION
The slides will be published on ClassRoom. Course

1) M. Sispser, "Introduction to the Theory of Computation"

2) H. Lewis, C. Papadimitriou, "Elements Of The Theory Of Computation", 2Nd Edition