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.