MAC 828 Tópicos em Complexidade Computacional

Conteúdo das Aulas durante o mês de agosto

• Aula 1 (10 de agosto)
  • Provas Interativas
    • Jogos de Artur e Merlin
    • Sistemas de Provas Interativas
  • Definição das classes IP(t(n)), AM(t(n)), IP e AM
  • Sistemas de Provas Interativas
    • NP \subseteq IP(2) \subseteq IP
    • Exemplo: Grafo Não-Isomorfismo (a ser continuado...)
• Aula 2 (12 de agosto)
  • co-NP \subseteq IP
    • Prova: O seguinte problema está em IP: dado um grafo, seu número cromático é maior ou igual a 4?
• Aula 3 (17 de agosto)
  • co-NP \subseteq IP (continuação...)
• Aula 4 (21 de agosto)
  • IP = PSPACE
    • Prova:
      IP \subseteq PSPACE: direto
      PSPACE \subseteq IP: QBF é PSPACE-completo, IP fechado em relação a reduções, QBF \in IP
• Aula 5 (24 de agosto)
  • IP = PSPACE (continuação...)
• Aula 6 (28 de agosto)
  • Provas verificáveis probabilisticamente: as classes PCP(r(n),q(n))
  • PCP(log n, 1) \subset NP
• Aula 7 (31 de agosto)
  • O PCP teorema: relação com aproximação.
  • Teorema. Existe uma constante \epsilon tal que computar uma (1 + \epsilon)-aproximação para MAX-3SAT é NP-difícil.
  • Teorema. NP \subset PCP(n^3,1) (a ser continuado)