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
- 2017/2018
- 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.
- 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.
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.
(4 hours): LOGSPACE, NLOGSPACE, PSPACE e NPSPACE. The concept of transductor. Polynomial reductions. Satvich theorem.
(4 hours): EXPTIME, NEXPTIME, EXPSPACE, NEXPSPACE. Separation theorems. Didactic methods
- Lectures. This is a highly theoretical course that is approached in class with participative lectures and solutions of problems of increasing difficulty.
Learning assessment procedures
- Oral exam. During the exam 4/5 questions (valued between 4 and 8 thirtieths each) will be asked. The candidate will undergo a 30 minutes (more or less) long interview in which he/she will be asked to solve some exercise seen in class, with particular attention to the veerification that the candidate has understood the most general and abstract concepts.
Reference texts
- *************** ATTENTION
The slides will be published on ClassRoom. Course code: 52bbrtr
***************
1) M. Sispser, "Introduction to the Theory of Computation"
2) H. Lewis, C. Papadimitriou, "Elements Of The Theory Of Computation", 2Nd Edition