Sumários

Aula Teórica 25

10 dezembro 2013, 13:00 • Maria Paula Antunes Abrantes Gouveia

Demonstração de que a função \(f:\mathbb{N}\to \mathbb{N}\) dada por \(f(n)=n\) é construtível no espaço. Funções construtíveis no tempo. Teorema de hierarquia no tempo. Demonstração de que a conversão de máquinas de Turing multifita em máquinas de Turing com uma fita equivalentes se pode fazer com custo quadrático.

Aula Teórica 24

5 dezembro 2013, 12:30 • Maria Paula Antunes Abrantes Gouveia

Referência à conversão de máquinas de Turing não determinísticas em máquinas de Turing determinísticas com incremento exponencial no tempo. Referência ao teorema de Savitch. Linguagens C-difíceis e  C-completas. Relevância das linguagens NP-completas. Exemplos de linguagens NP-completas (SAT e existencia de caminhos hamiltonianos num grafo). Funções construtíveis no espaço. Teoema de hierarquia no espaço.

Exercícios sobre classes de complexidade

3 dezembro 2013, 14:30 • João Rasga

Resolução dos exercícios 1.1.a, 1.1.b, 1.1.c, 1.3.c e 1.3.a.

Aula Teórica 23

3 dezembro 2013, 13:00 • Maria Paula Antunes Abrantes Gouveia

Tese de Cobham e versão forte do postulado de Church-Turing. Referência à conversão de máquinas de Turing multifita em máquinas de Turing com uma fita equivalentes com incremento polinomial no tempo. Breve referência à conversão de outros modelos de computação deterministicos a uma máquina de Turing. Máquina de Turing não determinística: palavras aceites e linguagem reconhecida. Classificador não determinístico. Exemplo. As classes NTIME(t), NSPACE(s), NP e NPSPACE. Referência às inclusões P\(\subseteq\) NP\(\subseteq\) PSPACE=NPSPACE\(\subseteq\) EXPTIME e aos problemas em aberto relativos às inclusões estritas.

Aula Teórica  22

28 novembro 2013, 12:30 • Maria Paula Antunes Abrantes Gouveia

Classes de funções PF e PSPACEF. Redução polinomial. Fecho de P, SPACE e NP para a redução polinomial. Demonstração do caso PSPACE.