Sumários

17 Dezembro 2019, 11:00 • Andreia Mordido

Resolução de exercícios sobre classes de complexidade.

17 Dezembro 2019, 10:30 • André Souto

Resolução de exercícios sobre classes de complexidade da folha 10.

17 Dezembro 2019, 09:30 • André Souto

A questão P vs NP.Noção de redução polinomial.

Consequências de existência de reduções polinomiais entre problemas.

Noção de problema NP-completo e o problema SAT e 3SAT.

Prova que 3SAT é polinomialmente redutível a CLIQUE.

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.

16 Dezembro 2019, 08:00 • André Souto

Resolução de exercícios sobre classes de complexidade da folha 10.

13 Dezembro 2019, 11:30 • Andreia Mordido

Resolução de exercícios sobre reduções por mapeamento entre linguagens.