Computability and Complexity
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2021/2022 - 2S
Cycles of Study/Courses
Teaching language
Portuguese
Objectives
Study and comparison of different (Turing-complete) models of computation, their computational power and limitations. Study of the various complexity classes of problems.
After completing this course students are expected to
- know the classical models of computation;
- be able to prove the equivalence of several Turing-complete models;
- know the fundamental results and methods used in the study of computability and complexity;
- be able to classify concrete examples of problems and prove their (un)decidability within several classes of computability;
- be able to classify concrete problems about their time complessity, and understand the consequences of that classification.
Learning outcomes and competences
Students are exposed to different standard Turing-complete models of computation, such as register machines, Turing machines e recursive functions. Besides proving the equivalence of those models, they also are used to identify different undecidable problems. For this, different techniques, such as the diagonalization method and the reduction between languages are used. In order to gain experience identifying the computational complexity of concrete problems, students are introduced to the classes P and NP, the notion of NP-completeness and Cook’s theorem, revisiting again the reduction technique.
Working method
Presencial
Pre-requirements (prior knowledge) and co-requirements (common knowledge)
Knowledge of some models of computation such as Finite Automata, Regular Expressions and Context-free Grammars. Basic notions of Logic.
Program
Notion of (semi-)decidable language/problem. Revision of some models of computation (DFA, NFA, CFG and PDA) and their power of computation. Register machines. Turing machines. Recursion theory. Lambda Calculus. Church-Turing thesis. Chomsky hierarchy. Kleene's Recursion Theorem. The diagonalization method and the indecidability of the halting-problem. Reduction “many to one” between languages. Introduction to complexity theory: P and NP classes, NP-completeness, Cook’s theorem and other NP-complete problems. Class co_NP, etc.
The PSPACE class.
Mandatory literature
Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullmann.
Recursion theory, Phillips, in Handbook of logic in computer science (vol. 1), Oxford University Press.
Complementary Bibliography
Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.
Oded Goldreich; P, NP, and NP-Completeness - The Basics of Computational Complexity, Cambridge University Press, 2010
Teaching methods and learning activities
Lectures: exposition of the elements in the syllabus.
Lab classes: resolution of exercises proposed each week.
Evaluation Type
Distributed evaluation without final exam
Assessment Components
designation |
Weight (%) |
Teste |
100,00 |
Total: |
100,00 |
Amount of time allocated to each course unit
designation |
Time (hours) |
Estudo autónomo |
106,00 |
Frequência das aulas |
56,00 |
Total: |
162,00 |
Eligibility for exams
No specific requirements to attend exams.
Calculation formula of final grade
First test (50% of the final mark).
Second test (50% of the final mark).
If FT is the mark obtained in the first test and ST the mark obtained in second test, then the final mark is given by:
F = FT*(0.5) + ST*(0.5)
FT,ST >= 6 and F >= 9.5
To get approval in the distributed evaluation, students must obtain a minimum of 6 points (in a total of 20) in each test and a minimum of 9.5 as final mark.
The students not obtaining approval, can take a resit exam, with a weight of 100% of the final mark.
Additionally there could be lab projects proposed in each module, with the weight of these projects in the final mark to be determined by the teacher.