# FORMAL LANGUAGES, COMPUTABILITY AND COMPLEXITY

If you can't find the course description that you're looking for in the above list, please see the following instructions >>
Versione italiana
2022/2023
Teacher
GUIDO SCIAVICCO
Credits
6
Didactic period
Secondo Semestre
SSD
INF/01

#### 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

#### Prerequisites

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.

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