Sumários

14 Dezembro 2018, 11:30 • André Souto

Resolução de exercícios da folha 9 e 10 sobre reduções e complexidade.

14 Dezembro 2018, 08:00 • André Souto

Resolução de exercícios da folha 9 e 10 sobre reduções e complexidade.

12 Dezembro 2018, 09:30 • André Souto

Diferença entre encontrar uma prova e verificar uma prova de pertença a uma linguagem.

Noção de verificador de tempo polinomial.

Definição formal da classe NP baseada em verificadores de tempo polinomial.

A questão P vs NP e as suas implicações.

Exemplos de problemas em NP.

Prova que HAMPATH e CLIQUE e FACTORIZATION e (3)SAT estão em NP.

Noção de tempo em máquinas não deterministas como motivação para definição alternativa da classe NP.

Prova que NP é a classe das linguagens aceites por uma máquina não determinista de tempo polinomial.

Noção de completude de problemas NP.

12 Dezembro 2018, 08:00 • André Souto

Resolução de exercícios da folha 9 e 10 sobre reduções e complexidade.

11 Dezembro 2018, 11:00 • Andreia Mordido

Resolução de exercícios da folha 9 e 10 sobre reduções e complexidade.