Sumários

21 Dezembro 2016, 09:30 • Ana Respicio

A classe P versus NP.

Redução em tempo polinomial.

Teorema 7.31, Sipser. Prova.

NP-completude.

Definição de linguagem NP-completa.

Linguagens NP-completas.

Resolução do exame do ano anterior.

21 Dezembro 2016, 08:00 • Ana Respicio

Folha 10: exercícios 1, 2, 3, 4, 5, 6

20 Dezembro 2016, 11:00 • Alexandre Miguel dos Santos Martins Pinto

Folha 10: exercícios 1, 2, 3, 4, 5, 6

20 Dezembro 2016, 10:30 • Ana Respicio

Folha 10: exercícios 1, 2, 3, 4, 5, 6

20 Dezembro 2016, 09:30 • Ana Respicio

A linguagem PATH. PATH pertence a P. Prova.

A classe NP. Verificadores.

A linguagem HAMPATH. HAMPATH pertence a NP.

Teorema 7.20.

NTIME(t(n)).

Exemplos de problemas em NP.