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.