014-2005

MO640 - Questão para a prova oral
Número: 014
Sobre a classe de problemas NP, três 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" (João Meidanis em aula)
(II) "Problemas da classe NP possuem algoritmos não-determinísticos polinomiais que os resolvem" (Cid Souza 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?

1. somente I
2. somente III
3. I e II
4. I, II e III
5. NDA

Autor(a): Tony Minoru Tamura Lopes