Completude NP
16 Dezembro 2020, 09:30 • André Souto
Noção de problema NP-completo e o problema SAT e 3SAT.
Formas de provar que um problema é NP-completo.
Prova que A\leq_p B e A é NP e B é P então P=NP.
Prova que A\leq_p B e A é NP-completo e B é NP então B é NP completo.
Enunciado e ideia da prova de que 3SAT é NP-completo.
Resolução de exercícios tipo de exame sobre esta matéria.
Aula em regime não presencial síncrono transmitida via zoom.