Tópicos em Complexidade Computacional

Professor Murilo V. G. da Silva
Dias/Horários das Aulas: 3as e 5as -- 13h30 às 15h00
Local: DINF - sala 103

Cronograma previsto:

(07/05) Apresentação da disciplina
Leitura: [AB09] Introdução e Cap.0.
[slides 01]

(14/06) Universalidade e Eficiência da Universalidade de Máquinas de Turing
Leitura: [AB09]: Início até sec 1.5; sec 1.7
[slides 02]

(21/06) As classes P, NP e EXP; Completude de problemas
Leitura: [AB09]: sec 1.6, 2.1, 2.2
[slides 03]

(23/06) As classes P, NP e EXP; Completude de problemas (cont.)
Leitura: [AB09]: sec 1.6, 2.1, 2.2
(conteúdo nos slides da aula passada)

(28/06) As classes coNP e NEXP;
Leitura: [AB09]: sec 2.6, 2.7
[slides 04]

(30/06) Teoremas de Hierarquia
Leitura: [AB09]: 3.1, 3.2
[slides 05]

(05/07) Teorema de Ladner e Problemas NP-intermediários
Leitura: [AB09]: sec 3.3.
[slides 06]

(07/07) Teorema de Baker-Gill-Solovay, Oráculos e o Mundo Relativizado
Leitura: [AB09]: sec 3.4, cap. 4
[slides 07]

(12/07) Teorema de Cook-Levin; Problemas de Busca
Leitura: [AB09]: sec 2.3, 2.4, 2.5
[slides 08]

(28/07) Complexidade de Espaço
Leitura: [AB09]: cap. 4
[slides 09]

(02/08) A Hierarquia Polinomial (cont.)
Responsável: T.B.A.
Leitura: [AB09]: cap. 5
[slides 10]

(04/08) A Hierarquia Polinomial (cont.)
Responsável: T.B.A.
Leitura: [AB09]: cap. 5
(conteúdo nos slides da aula passada)

(09/08) Circuitos booleanos e computação não uniforme (cont.)
Leitura: [AB09]: cap. 6
[slides 11]

(11/08) As classes BPP, RP, coRP e ZPP
Leitura: [AB09]: cap. 7
[slides 12]

(16/08) Arthur, Merlin e Provas Interativas
Leitura: [AB09]: cap. 8
[slides 13]

(19/08) Arthur, Merlin e Provas Interativas (cont.)
Leitura: [AB09]: cap. 8
Slides: (conteúdo nos slides da aula passada)

(22/08) Provas de Conhecimento Zero e Criptografia
Leitura: [AB09]: cap. 9
Slides: aula sem slides


(25/08,30/08, 01/09) Apresentação de trabalhos



Bibliografia