car

MO417 - Questão para a prova oral

Número:

Enunciado: Leia as seguintes afirmações:

I.- Uma forma de provar que um problema é NP-completo, é fazer-lhe uma redução ate um problema de decisão.
II.- O fechamento da estrela de Kleene de uma linguagem L é a linguagem L*= L¹ U L² U L³ U ...
III.- A classe NP tem problemas que som certificados por um algoritmo que corre em tempo polinomial.

Escolha a alternativa correta.

a) I y II são verdadeiras.
b) Apenas III e verdadeira.
c) II e III não são falsas.
d) I, II e III são verdadeiras.
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales