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
