Sumários

AP28 Complexidade de Kolmogorov

19 dezembro 2013, 16:00 Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre complexidade de Kolmogorov (restantes requisitos).


AT28 - Introdução à complexidade computacional (conc)

19 dezembro 2013, 11:30 Amilcar Sernadas

Classes aD, aP e aEXP. Teorema da hierarquia.Linguagem certificada por outra linguagem. Aplicação testemunha. Linguagem certificável com recurso limitado por aplicação construtível. Classes aND, aNP e aNEXP. Enquadramento polinomialmente bem comportado. Inclusão de aP em aNP. Classe acoNP. Redutibilidade polinomial à Karp e à Cook. Graus versus classes de complexidade. Dureza e completude. NP-completude. Propriedades básicas. Tempo de computação como recurso. Classes D, P, EXP, NP e coNP. Exemplos. Enunciado do teorema de Cook-Levin. Espaço de computação como recurso. Classes DSPACE, PSPACE = NPSPACE = coNPSPACE e EXPSPACE.


AP27 Complexidade de Kolmogorov

17 dezembro 2013, 14:30 Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre complexidade de Kolmogorov (envolvendo os requisitos (R3) a (R7).


AT27 - Introdução à complexidade computacional

17 dezembro 2013, 11:00 Amilcar Sernadas

Conclusão da aula anterior: resultados básicos, robustez da noção de complexidade descritiva (teorema da invariância) e incompressibilidade.
Função universal própria com recurso limitado. Enquadramento de computação com recurso limitado. Aplicação construtível. Aplicação computável com recurso limitado por aplicação construtível. Linguagem decidível com recurso limitado por aplicação construtível.


AP26 Redutibilidade à Turing

12 dezembro 2013, 16:00 Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre redutibilidade à Turing.