Complexidade Temporal

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.