NP-completude

21 Dezembro 2016, 09:30 Ana Respicio

A classe P versus NP.

Redução em tempo polinomial.
Teorema 7.31, Sipser. Prova.
NP-completude.
Definição de linguagem NP-completa.
Linguagens NP-completas.
Resolução do exame do ano anterior.