Cronograma de Complexidade

Março

Abril

Maio

Junho

• 5 de junho (Aula 18):
  • Problemas NP-completos (cap 9 do Papa)
  • Prop (certificados curtos): L está em NP sse existe uma relação R polinomialmente decidível e polinomialmente balanceada tq L = {x: (x,y) \in R para algum y}.
  • Variantes do SAT e sua complexidade: 3-SAT é NP-completo, 3-SAT com variáveis aparecendo no máximo 3 vezes é NP-completo, 2-SAT está em P, MAX2-SAT é NP-completo.
  • Lista 4.
• 7 de junho (Aula 19):
  • Problemas em grafos NP-completos: INDEPENDENT SET, CLIQUE, VERTEX COVER, MAXCUT, MAX BISSECTION.
• 12 de junho (Aula 20):
  • HAMILTON PATH, TSP e 3DM são NP-completos.
• 14 de junho (Aula 21):
  • coNP e function problems (cap 10 do Papa)
  • PRIMES está em NP e em coNP.
  • algoritmos pseudopolinomiais x fortemente polinomiais.
• 19 de junho (Aula 22):
• 21 de junho (Aula 23):
• 26 de maio (Aula 24):
  • Revisão para a prova.
• 28 de maio:
  • Prova 3.