Classe de Complexidade NP
12 Dezembro 2018, 09:30 • André Souto
Diferença entre encontrar uma prova e verificar uma prova de pertença a uma linguagem.
Noção de verificador de tempo polinomial.
Definição formal da classe NP baseada em verificadores de tempo polinomial.
A questão P vs NP e as suas implicações.
Exemplos de problemas em NP.
Prova que HAMPATH e CLIQUE e FACTORIZATION e (3)SAT estão em NP.
Noção de tempo em máquinas não deterministas como motivação para definição alternativa da classe NP.
Prova que NP é a classe das linguagens aceites por uma máquina não determinista de tempo polinomial.
Noção de completude de problemas NP.