Teoria de Complexidade Computacional

Grupo de Estudos do ARG

Horários dos Encontros: 2a-feira (13h30 -- 15h00)
Local: PC-18

Primeiro Semestre de 2019:

(11/03) Modelos de Computação, Universalidade e Eficiência da Universalidade
Responsável: Murilo
Leitura: [AB09]: Início até sec. 1.5, sec 1.7
Material: [Rascunho em pdf]

(18/03) Classes P, NP, coNP, PSPACE, NP-completude
Responsável: Henrique
Leitura: [AB09]: sec 1.6, 2.1, 2.2, 2.5
Material: [Slides em pdf]

(25/03) EXP, NEXP e Teoremas de Hierarquia
Responsável: Murilo e Nicollas
Leitura: [AB09]: sec 2.6, 3.1, 3.2
Material: [Rascunho em pdf] [Manuscrito em pdf]

(01/04) Teorema de Cook-Levin
Responsável: Leandro
Leitura: [AB09]: sec 2.3; [PAP93]: Cap. 8
Material: [Cap. Livro] [Manuscrito em pdf]

(08/04) Teorema de Ladner e Problemas NP-intermediários
Responsável: Nicollas e Murilo
Leitura: [AB09]: sec 3.3
Material: [Manuscrito em pdf]

(15/04) Teorema de Baker-Gill-Solovay e Provas relativizantes
Responsável: Murilo
Leitura: [AB09]: sec 3.4
Material: T.B.A.

(22/04) Complexidade de Espaço
Responsável: Leandro
Leitura: [AB09]: cap. 4
Material: [Manuscrito em pdf]

(29/04) Complexidade de Espaço (cont.)
Responsável: Leandro
Leitura: [AB09]: cap. 4
Material: [Manuscrito em pdf]

(20/05) A Hierarquia Polinomial
Responsável: Murilo
Leitura: [AB09]: cap. 5
Material: T.B.A.

(03/06) A Hierarquia Polinomial (cont.)
Responsável: Murilo e Nicollas
Leitura: [AB09]: cap. 5
Material: [Manuscrito em pdf]

(10/06) Circuitos booleanos e computação não uniforme
Responsável: Murilo e Nicollas
Leitura: [AB09]: cap. 6
Material: [Manuscrito em pdf]

(17/06) As classes BPP, RP, coRP e ZPP
Responsável: Murilo e Nicollas
Leitura: [AB09]: cap. 7
Material: N.A.

(24/06) Arthur, Merlin e Provas Iterativas (parte 1)
Responsável: Nicollas
Leitura: [AB09]: cap. 8
Material: [Slides em pdf] [Manuscrito em pdf]

(08/07) Arthur, Merlin e Provas Iterativas (parte 2)
Responsável: Murilo e Nicollas
Leitura: [AB09]: cap. 8
Material: T.B.A.

Segundo Semestre de 2019 (cronograma previsto):

(12/08) Arthur, Merlin e Provas Iterativas (parte 3)
Responsável: Murilo
Leitura: [AB09]: cap. 8
Material: T.B.A.

(19/08) Classes de Complexidade Quânticas: BQP, QMA e outras
Responsável: Henrique
Leitura: [MI17]: Cap. 14
Material: T.B.A.

(26/08) Complexidade de Rademacher
Responsável: Alane
Leitura: [MI17]: Cap. 14
Material: T.B.A.

(02/09) Complexidade de Kolmogorov
Responsável: Murilo
Leitura: cap. 1 do Li e Vitani
Material: T.B.A.

(09/09) Complexidade de Contagem, Parte 1: #P e PP
Responsável: Henrique
Leitura: [AB09]: cap. 17
Material: T.B.A.

(16/09) Complexidade de Contagem, Parte 2: Teorema de Valiant
Responsável: Murilo
Leitura: [AB09]: cap. 17
Material: T.B.A.

(16/09) Complexidade de Contagem, Parte 3: Teorema de Toda
Responsável: Murilo
Leitura: [AB09]: cap. 17
Material: T.B.A.

Bibliografia