# FORMAL LANGUAGES, COMPUTABILITY AND COMPLEXITY

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