Sumários

13 Dezembro 2019, 08:00 • Andreia Mordido

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

13 Dezembro 2019, 08:00 • André Souto

Resolução de exercícios da folha 9 sobre reduções por mapeamento entre problemas.

11 Dezembro 2019, 09:30 • André Souto

Noção de verificador de tempo polinomial.

Definição de certificado.

Definição de problemas da classe NP como sendo a classe de problemas que admitem um verificador de tempo polinomial.

Exemplos de linguagens em NP.

Recordar a noção de tempo de execução numa máquina não determinista.

Noção de problema em NP via máquinas não deterministas.

Prova que as duas definições de NP são equivalentes.

Mais exemplos de problemas em NP.

11 Dezembro 2019, 08:00 • André Souto

Resolução de exercícios da folha 9 sobre reduções por mapeamento entre problemas.

10 Dezembro 2019, 11:00 • Andreia Mordido

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