Classe NP
15 Dezembro 2020, 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.
Noção de redução polinomial.
Consequências de existência de reduções polinomiais entre problemas.
Consequências de existência de reduções polinomiais entre problemas.
Aula em regime não presencial síncrono transmitida via zoom.