Complements of Computational Complexity
Code
9644
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Oleksiy Karlovych
Teaching language
Português
Objectives
At the end of this course students will have acquired advanced knowledge and skills in the area of computational complexity in order to:
- Understand advanced contents in the area;
- Being able to execute research on a topic in the area.
Subject matter
Computation models: sequencial, non-deterministic, and parallel.
Classes of computational complexity (like FPtime, P, NP, PH, Pspace, FPspace, NC^k, NC, AC^k, AC, Logspace, among others).
Machine independent characterizations: Cobham characterization of FPtime, Thompson characterization of FPspace, Clote-Takeuti approach to parallel classes, etc.
Implicit characterizations.
Bibliography
S. Bellantoni, Predicative Recursion and Computational Complexity. Ph. D. Dissertation, University of Toronto, 1993.
S. Buss and P. Scott, Feasible Mathematics, Birkhäuser, 1990.
N. Immerman, Descriptive Complexity, Springer, 1999.
C.H. Papadimitirou, Computational Complexity, Addison-Wesley, 1994.