3.  As soluções de problemas de aproximação garantem uma solução ótima dentro do aceitável e são conhecidas como soluções aproximadas para problema...

3. 

As soluções de problemas de aproximação garantem uma solução ótima dentro do aceitável e são conhecidas como soluções aproximadas para problemas, em que não são encontrados resultados em um tempo polinomial por meio de algoritmos deterministas (NP-completo).

Considerando o contexto apresentado, avalie as seguintes asserções sobre as soluções de problemas de aproximação:

I. As soluções aproximadas podem ser de minimização ou maximização se o problema tiver um custo positivo.

PORQUE

II. A solução para o problema de cobertura de vértices tem o objetivo de maximizar o maior número de arestas de um grafo.

A respeito dessas asserções, assinale a opção correta:

A. 

As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

B. 

As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.

C. 

A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.

D. 

A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

E. 

As asserções I e II são proposições falsas.