Aula
Data
Bibliografia

Sumário/Notas

1/2
9/02/17
MTs e Comp
HU79, Cap 7,8
OG08, Cap 1
AB09 1.1-1.5

Simulador de TMs
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.
2
16/02/17
Classes pag 7-36
OG08 pp 44-70
GJ Cap 1 e 2
HU79, Cap 9
AB09 2

Classes de complexidade. Classes P e NP. Problemas em P e NP. Reduções polinomiais. Problemas NP-completos.
Sugestões
Resolver os exercícios de Classes das pág. indicadas.
3
24/02
Classes pag 37- 52
GJ Cap 2.6 e 3.1-3.2
OG08 pp 71-81
AB09 2.2-2.4

Teorema de Cook
Lista de Karp
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.
4
2/03
Classes
OG08 4.4,2.2,3.3,5.3
GJ Cap 5,7.1
AB09 2.6, 5
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
Classes pag 60-68
AB09 4
OG08 2.4.3,3.2.1, 3.2.2
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/
Classes Sec. 3.1-3.3
AB09 3, 4
HU79 12
OG08 5.1.1, 5.1.2,5.3.2
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
Classes Sec. 3.4
AB09 3.2,4.2,
Sipser 9.1, 8.3
OG08 4.2, 4.3, 5.3
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
Classes cap. 4
AB09 4.2, 5.3,5.4
Sipser 8.2-3
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.
9
6/04
Classes Cap 5.1-5.3.1
AB09 4.3- 61-6.2,6.7
OG08 5.2, 5.3.2, 3.1,3.2.3
Sipser 8.4-8.6, 9.3
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
Classes Sec. 5.3.2,5.3.3, 5.4
AB09 6.7, 17.1
P94 15.1-3,18.1
Sipser 10.5
OG08 6.2.1
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
Classes Cap. 6
AB09 7
P94 11
Sipser 10.2
OG08 6.1
Miller-Rabin
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
Classes Cap. 7
AB09 8.1-8.3
P94 19.2
Sipser 10.4
OG08 9.1
IP=PSPACE
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
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.