Aula
Data
Bibliografia
Sumário/Notas
1/2
9/02/17
Objectivos da disciplina e tópicos do programa. Métodos de avaliação. Bibliografia recomendada.
Problemas Decisão e Linguagens. Máquinas de Turing. Variações de Máquinas de Turing. Breve revisão de computatibilidade: problemas decidíveis (linguagens recursivas), semidecidíveis (linguagens recursivamente enumeráveis) e indecidíveis (linguagens não recursivamente enumeráveis); máquinas universais de Turing; reduções entre problemas. Teorema de Rice.
Problemas Decisão e Linguagens. Máquinas de Turing. Variações de Máquinas de Turing. Breve revisão de computatibilidade: problemas decidíveis (linguagens recursivas), semidecidíveis (linguagens recursivamente enumeráveis) e indecidíveis (linguagens não recursivamente enumeráveis); máquinas universais de Turing; reduções entre problemas. Teorema de Rice.
3
24/02
Problemas NP-completos. Teorema de Cook. Técnicas para mostrar a NP-completude de problemas.Exemplos de reduções : 3SAT, VC, CLIQUE, HC, 3DM e PAR.
Sugestões
Estudar a redução 3DM a PAR
Resolver os exercícios de Classes das pág. indicadas.
Resolver os exercícios de Classes das pág. indicadas.
4
2/03
A classe coNP e a estrutura de NP. Problemas de Procura. Máquinas de Turing com Oráculos. Reduções de Turing. A classe DP. Relativização de linguagens.
Sugestões
5
9/03
Relações entre NP e coNP. Relativização de linguagens. A hierarquia polinomial, PH. Colapso de PH. PH e completude. Problema completo para cada nível de PH.
Sugestões
6
16/03/
Complexidade em tempo de restrições ao número de fitas duma máquina de Turing. Complexidade em espaço. Relações entre diversas classes de complexidade em tempo e em espaço. Teorema de Savitch. PSPACE=NPSPACE.
7
23/03
Teoremas de Separação e Hierarquia para classes de complexidade determinísticas.Hierarquia para classes de complexidade não determinísticas. Teorema de Immerman-Szelepcsényi.
8
30/03
Alternância e Classes de complexidade alternada. Relação entre classes de complexidade. PSPACE e Completude. Complexidade de jogos de informação perfeita.
Hierarquias alternada e polinomial.
Hierarquias alternada e polinomial.
9
6/04
As Classes L e NL. Transdutores em espaço logarítmico. Reduções em espaço logarítmico. Completude relativas a reduções em espaço logarítmico. Circuitos Booleanos. Problemas P-completos. Famílias de circuitos. Classe P/poly. P-uniformidade.
10
20/04
Paralelismo e Classe NC. Tamanho e profundidade de circuitos. Algoritmos em NC de matrizes e inteiros. Relação com classes de complexidade em tempo e em espaço. Problemas de contagem . A classe #P.
11
27/04
Algoritmos aleatorizados. Máquinas de Turing Probabilísticas. Classes RP e BPP. Relação entre classes. Exemplos de algoritmos probabilisticos. Lema da Amplificação. BPP e PH
12
4/05
Sistemas Interactivos de Prova. A Classe IP. IP=PSPACE.
13
18/05
Classes Cap. 8
AB09 11
OG08 9.3 e 10.1
Approximation Algorithms 1,8, 29
Dinur’s proof PCP
Inapproximation (L. Trevisan)
Arora
AB09 11
OG08 9.3 e 10.1
Approximation Algorithms 1,8, 29
Dinur’s proof PCP
Inapproximation (L. Trevisan)
Arora
Aproximação de problemas de Optimização. Razão de aproximação e esquemas polinomiais. Exemplo: problemas da cobertura por vértices e Caixeiro Viajante.
Classe NP e não aproximação. PCP: Provas verificáveis probabilisticamente. Teorema PCP e dificuldade de aproximação. Não aproximação de MAX-3SAT e MAX-CLIQUE.
Classe NP e não aproximação. PCP: Provas verificáveis probabilisticamente. Teorema PCP e dificuldade de aproximação. Não aproximação de MAX-3SAT e MAX-CLIQUE.