Unit COMPUTABILITY AND COMPLEXITY

Course
Informatics
Study-unit Code
A002041
Curriculum
In all curricula
Teacher
Arturo Carpi
Teachers
  • Arturo Carpi
Hours
  • 42 ore - Arturo Carpi
CFU
6
Course Regulation
Coorte 2022
Offered
2022/23
Learning activities
Caratterizzante
Area
Discipline informatiche
Academic discipline
INF/01
Type of study-unit
Obbligatorio (Required)
Type of learning activities
Attività formativa monodisciplinare
Language of instruction
English
Contents
Turing machine. Goedel coding. Church-Turing thesis.
Unsolvable problems. Universal Turing machine. halting problem. Hilbert tenth problem. Partial recursive functions.

Edmonds-Cook-Karp thesis. Classes P and NP. NP complete problems. Classes L, NL, PSPACE, NPSPACE.
Reference texts
C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, Teoria della computabilità e della complessità, McGraw-Hill
J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson
M. Davis, Computability and Unsolvability, Dover (ediz. Italiana: Abete, 1974)
Michael Sipser, Introduction to the Theory of Computation, Cengage, 2013
Educational objectives
The course will furnish to the student the knowledge of the main methods and results of the Computability and Complexity Theory.

Moreover it will give the ability to apply this knowledge to identify the complexity of practical problems in various fields.
Prerequisites
In order to attend the course,the student should have some basic knowledge of Formal Language Theory and of algorithm complexity analysis.

This notions are present in the fundamental courses of the first level degree courses in Informatics.
Teaching methods
Lectures
Other information
-
Learning verification modality
The final evaluation consists is an oral exam.

The goal of this exam is to verify the acquisition of the main theoretical aspect of the discipline and the ability to apply such knowledge in order to evaluate the structural complexity of problems in different fields.
Moreover, the ability of discussing the themes of the course using a proper technical language will be evaluated.

On student request, exam may be given in Italian, English or French.
Extended program
Theory of computability:
Alphabets, strings, languages.
Turing machine. Turing machines and languages. Turing machines and functions. Goedel coding. Church-Turing thesis.
Multi-tape Turing machines. Non deterministic Turing machines.
Algorithmically solvable problems and unsolvable problems. Universal Turing machines. halting problem.
Decidable and semi-decidable sets. Hilbert tenth problem. Recursion theorem, fix-point theorem and Rice's theorem. Post correspondence theorem.
Recursive function. Church-computabilty. Partial recursive functions.

Complexity theory:
Time complexity classes. The class P and Edmonds-Cook-Karp thesis. The class NP. The problem P=NP. NP-completeness. Cook-levin theorem. Merkle-Helmann crypto-system.
Space complexity classes. The classes L, NL, PSPACE, NPSPACE. Savitch theorem.
Condividi su