Completude NP

18 Dezembro 2018, 09:30 • André Souto

Recordar a noção de problema NP com base no verificador e nas MT não deterministas.

Exemplos de problemas em NP e respectivos certificados, verificadores e MT não deterministas.
Noção de redução polinomial entre problemas. 
Prova que se A é P e B se reduz a A então B também é P.
Prova que se A é NP e B se reduz a A então B também é NP.
Definição de completude de problemas NP.
Exemplos de problemas NP-completos.
Prova que A é NP e B é NP-completo e se reduz a A então A também é NP -completo.
Exemplos de uso do Lema.Referência ao problema SAT e a sua completude.