A classe NP
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.