Disciplina Discipline MAC5850
Computabilidade e Tratabilidade via Lógica

Computability and Tractability via Logic

Área de Concentração: 45134

Concentration area: 45134

Criação: 25/06/2021

Creation: 25/06/2021

Ativação: 25/06/2021

Activation: 25/06/2021

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docente Responsável:

Professor:

Marcelo Finger

Objetivos:

Estudar os conceitos fundamentais de computação modelado do ponto de vista da Lógica Formal. Estudar as noções de funções compatíveis, problemas tratáveis e intratáveis, do ponto de vista da Lógica Formal.

Justificativa:

Há muitos problemas computacionais indecidíveis, e mesmo entre os decidíveis há uma larga classe de problemas intratáveis. Estes problemas se originaram no estudo de diversos fragmentos da lógica clássica: as lógicas de primeira e segunda ordem, e a lógica proposicional. Na formação básica de um aluno de pós-graduação, identificar e demonstrar a (in)computabilidade e (in)tratabilidade de um problema é uma habilidade fundamental, de grande interesse tanto teórico quanto prático.

Conteúdo:

1. Computabilidade: algoritmos, máquinas de Turing, funções recursivas primitivas e parciais. 2. Lógica: Proposicional, Primeira e Segunda Ordem. Satisfatibilidade, decidibilidade. Aritmética de Primeira Ordem. Funções Representáveis na Aritmética. Funções aritméticas recursivas e decidibilidade. 3. Teoremas de Incompletude Gödel. Incompletude de Lógica de Segunda Ordem. 4. Simulação de Máquinas de Turing em Lógica de Primeira Ordem. Indecidibilidade da Lógica de Primeira Ordem. 5. Tratabilidade: Máquinas de Turing não-determinística. Reduções polinomiais e a classe NP. Problemas NP-completos. Teorema de Cook-Levin. O fragmento existencial de Segunda Ordem e o Teorema de Fagin. 6. Lógica Booleana Quantificada e a caracterização lógica da classe PSPAÇO. 7. Hierarquias de complexidade: a hierarquia polinomial e sua caracterização em termos de fórmulas de Lógica Booleana Quantificada. Noções de classes Exponenciais. Noções de complexidade da classe não-elementar.

Forma de Avaliação:

Bibliografia:

[1] Walter Carnielli and Richard Epstein, Computabilidade, Funções Computáveis, Lógica e seus Fundamentos, Editora da UNESP. 2005. [2] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness, W.H. Freeman and Company, New York, 1979, 338p. [3] George S. Boolos and Richard C. Jeffrey, Computability and Logic, third edition ed., Cambridge University Press, 1989. [4] Christos H. Papadimitriou, Computational Complexity, Addison Wesley, 1994. [5] Stephen Cole Kleene, Introduction to metamathematics, Bibl. Matematica, North-Holland, Amsterdam, 1952.

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial