Tópicos de Lógica Matemática
Código
10848
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Reinhard Kahle
Total de horas
56
Língua de ensino
Português
Objectivos
Nesta disciplina abordam-se tópicos de lógica matemática e de complexidade computacional que lançam os fundamentos para assuntos da investigação actual nas áreas.
Pré-requisitos
Recomenda-se que os alunos tenham alguns conhecimentos preliminares de Lógica e Complexidade.
Conteúdo
Uma selecção adequada dos seguintes tópicos: cálculo de Tait, eliminação do corte, análise de ordinais, impredicatividade de sistemas axiomáticos, colapso de números ordinais, compreensão Pi^1_2; modelos de computação: sequenciais, não-deterministas e paralelos. Classes de complexidade computacional (como FPtime, P, NP, PH, Pspace, FPspace, NC^k, NC, AC^k, AC, Logspace, entre outras). Caracterizações independentes de máquinas: caracterização de Cobham para FPtime, de Thompson para FPspace, de Clote para classes paralelas, etc. Caracterizações implícitas.
Bibliografia
1. Handbook of Mathematical Logic (J. Barwise, ed.), North-Holland, 1977.
2. W. Pohlers, Proof Theory: An Introduction, Springer, 2002.
3. N. Immerman, Descriptive Complexity, Springer, 1999.
4. S. Bellantoni, Predicative Recursion and Computational Complexity. Ph. D. Dissertation, University of Toronto, 1993.
5. C.H. Papadimitirou, Computational Complexity, Addison-Wesley, 1994.
6. S. Buss and P. Scott, Feasible Mathematics, Birkäuser, 1990.