tia

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dentre as alternativas abaixo, assinale a INCORRETA.

A) A classe de problemas NP pode ser definida como o conjunto de problemas de decisão que podem ser solucionados em tempo polinomial em uma Máquina de Turing não determinística.

B) Um problema c em NP também está em NPC se e somente se todos os outros problemas em NP podem ser transformados em p em tempo polinomial.

C) A classe de problemas P engloba todos os problemas de decisão que podem ser resolvidos por um algoritmo de tempo polinomial.

D) A classe de problemas NPC é um subconjunto dos problemas de decisão em NP de tal modo que todo problema em NP pode-se reduzir, com uma redução de tempo polinomial, a um dos problemas NPC.

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade