Complexidade Computacional

Pós-graduação. 1o. Semestre de 2007

Sinopse das aulas

• Março
  1. (Aula 0) 6/3/2007 Discussão inicial sobre a disciplina. Veja informações gerais sobre esta edição [PS | PDF].
  2. (Aula 1) 8/3/2007 Definição de máquina de Turing. Funções tempo-construtíveis. Variante de máquinas de Turing.
  3. (Aula 2) 13/3/2007 Máquinas de Turing universais. Funções não computáveis e o problema da parada. Definição das classes DTIME e P.
  4. (Aula 3) 15/3/2007 Definição da classe NP. Exemplos de linguagens em NP. Relações entre NP, P e DTIME(2^{n^k}). Reduções de Karp e NP-completude. Um exemplo de problema NP-completo.
  5. (Aula 4) 20/3/2007 Definição de máquinas de Turing não-determinísticas. Definição de NTIME. Relação entre NP e NTIME. Teorema de Cook-Levin (enunciado e "false start").
  6. (Aula 5) 22/3/2007 Teorema de Cook-Levin (demonstração).
  7. (Aula 6) 27/3/2007 Algumas reduções de SAT e 3SAT (programação inteira, conjunto independente, caminho hamiltoniano dirigido). Decisão e busca.
  8. (Aula 7) 29/3/2007 Definição de coNP, EXP e NEXP. Prova de que, se EXP é diferente de NEXP, então P é diferente de NP.

• Abril
  1. 3/4/2007 Semana Santa

  2. 5/4/2007 Semana Santa

  3. (Aula 8) 10/4/2007 Diagonalização. Funções espaço-construtíveis. Definição da classe SPACE. Enunciado dos seguintes resultados (e prova de versões mais fracas):
     1. Dadas funções f e g tempo-construtíveis com f log f = o(g), vale que DTIME(f) está contido propriamente em DTIME(g).
     2. Dadas funções f e g espaço-construtíveis com f = o(g), vale que SPACE(f) está contido propriamente em SPACE(g).
     3. Dadas funções f e g tempo-construtíveis com f(n+1) = o(g(n)), vale que NTIME(f) está contido propriamente em NTIME(g).
  4. (Aula 9) 12/4/2007 Teorema de Ladner (demonstração).
  5. (Aula 10) 17/4/2007 Máquinas de Turing com oráculo. Prova de que existem oráculos A e B tais que P^A é igual a NP^A e P^B é diferente de NP^B.
  6. (Aula 11) 19/4/2007 Complexidade de espaço. Definição de NSPACE. Relações de DTIME, SPACE e NSPACE. Definição de PSPACE, NPSPACE, L e NL. Problemas PSPACE-completos e TQBF.
  7. (Aula 12) 24/4/2007 Hierarquia polinomial. Definição de \Sigma_i^p e \Pi_i^p. Definição de PH. Prova de que, se \Sigma_i^p = \Pi_i^p, então PH = \Sigma_i^p. Prova de que, se P = NP, então PH = P. Problemas completos para \Sigma_i^p e \Pi_i^p.
  8. (Aula 13) 26/4/2007 Circuitos. Definição de circuito booleano. Definição das classes SIZE e P/poly. Funções log-espaço computáveis. Famílias de circuitos log-espaço uniforme. Enunciado do teorema que diz que P é a classe de linguagens que adimitem famílias de circuitos log-espaço uniformes. Máquinas de Turing com sugestão.

• Maio
  1. 1/5/2007 Feriado

  2. 3/5/2007 Semana de break

  3. (Aula 14) 8/5/2007 Prova de que se NP está contido em P/poly, então PH colapsa no segundo nível. Cotas inferiores para circuitos.
  4. (Aula 15) 10/5/2007 Definição das classes BPTIME e BPP. Definição das classes RTIME, RP e coRP. Definição das classes ZTIME e ZPP. Relaçoes de ZPP, RP e coRP. Amplificação de probabilidade usando a desigualdade de Chernoff. Teorema de Adleman (enunciado).
  5. (Aula 16) 15/5/2007 Amplificação de probabilidade usando a desigualdade de Chernoff. Prova de que BPP está em \Sigma_2^p e em \Pi_2^p (início da demonstração).
  6. (Aula 17) 17/5/2007 Prova de que BPP está em \Sigma_2^p e em \Pi_2^p (fim da demonstração). Reduções probabilísticas. Definição de BPNP. Definição de NP/poly.
  7. (Aula 18) 22/5/2007 Sistemas interativos de provas. IP está contido em PSPACE (esquema de prova).
  8. (Aula 19) 24/5/2007 Sem aula.
  9. (Aula 20) 29/5/2007 IP contém PSPACE. Prova de que #SAT está em IP.
  10. (Aula 21) 31/5/2007 Arthur-Merlin. Famílias universais de funções de hashing. Protocolo de Goldwasser-Sipser.

• Junho
  1. 5/6/2007 Semana de break

  2. 7/6/2007 Corpus Christi

  3. (Aula 22) 12/6/2007 Grafos expansores. Definição de (n, d, \lambda)-grafos. Propriedades de (n,d,\lambda)-grafos.
  4. (Aula 23) 14/6/2007 Amplificação da probabilidade de acerto para linguagens em RP usando (n, d, \lambda)-grafos. Gerador de Ajtai-Komlós-Szemerédi
  5. (Aula 24) 19/6/2007 Amplificação de lacunas em resultados de aproximação. Prova do teorema de Feige-Wigderson-Alon-Zuckerman.
  6. (Aula 25) 21/6/2007 Prova do teorema de Feige-Wigderson-Alon-Zuckerman (continuação).

Calendário

   February 2007              March 2007               April 2007     
Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
             1  2  3                  1  2  3      1  2  3  4  5  6  7 
 4  5  6  7  8  9 10      4  5  6  7  8  9 10      8  9 10 11 12 13 14 
11 12 13 14 15 16 17     11 12 13 14 15 16 17     15 16 17 18 19 20 21 
18 19 20 21 22 23 24     18 19 20 21 22 23 24     22 23 24 25 26 27 28 
25 26 27 28              25 26 27 28 29 30 31     29 30

      May 2007                June 2007          
Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     
       1  2  3  4  5                     1  2     
 6  7  8  9 10 11 12      3  4  5  6  7  8  9     
13 14 15 16 17 18 19     10 11 12 13 14 15 16     
20 21 22 23 24 25 26     17 18 19 20 21 22 23     
27 28 29 30 31           24 25 26 27 28 29 30    

Last modified: Wed Aug 15 19:20:43 BRT 2007