MO640 - Questão para a prova oral
Número: 014
Sobre a classe de problemas NP, 3 definições são fornecidas por docentes da UNICAMP: (I) "Um problema se classifica como NP se for possível verificar a validade de um certificado de solução em tempo polinomial no tamanho da entrada". Meidanis em aula. (II) "Problemas da classe NP possuem algoritmos não-determinísticos polinomiais que os resolvem". Cid em aula. (III) "Os problemas cujas melhores soluções até então conhecidas demandam algoritmos com complexidade exponencial constituem a classe de problemas NP". Docentes da FEEC no Livro: Introdução a Sistemas de Computação Digital, 1999. Como todas fontes são 'renomadas', surge a dúvida: Quais definições estão corretas?
Autor(a): Tony Minoru Tamura Lopes