Cronograma de Complexidade
Primeiro semestre de 2002
Março
Abril
Maio
- 8 de maio (Aula 12):
- E(M): linguagem enumerada por uma MT M.
- Prop: L é r.e. sse existe M tq L=E(M).
- Teo: Seja L não-vazia uma linguagem r.e. O seguinte problema é
indecidível: dado M, L é a linguagem aceita por M?
- Lista 3.
- 10 de maio (Aula 13):
- Capítulo 8 do Papa: reduções.
- Redução do Circuito Hamiltoniano para o SAT.
- Definição de circuit value e circuit sat.
- 15 de maio (Aula 14):
- Redução do st-conexidade para circuit value, de circuit
sat para sat e de circuit value para circuit sat.
- Transitividade de reduções.
- 17 de maio (Aula 15):
- 22 de maio (Aula 16):
- 24 de maio:
- 29 de maio (Aula 17):
Junho
Last modified: Wed Jun 5 10:45:42 EST 2002