Question

1- Como é chamado um problema NP-Completo para o qual a existência de um algoritmo pseudopolinomial que o decida implica na existência de um algoritmo polinomial que o decida?

Assinale a alternativa correta.

Escolha uma:
a.
NP-difícil

b.
NP-Completo forte

c.
NP-Completo

d.
P-completo

e.
PSPACE

2-Uma linguagem B é NP-completa se ela satisfaz duas condições:

1. B está em NP, e

2. toda A em NP é ____________ em tempo ____________ a B.

Assinale a alternativa que preenche corretamente as lacunas.

Escolha uma:
a.
solúvel / recursivo

b.
redutível / polinomial

c.
insolúvel / polinomial

d.
redutível / exponencial

e.
solúvel / exponencial

3-Sobre a classe de problema NP-completo, analise as afirmativas a seguir.

I. Se algum problema em NP requer mais tempo polinomial, um NP-completo requer tempo exponencial.

II. Para provar que P é igual a NP somente precisa encontrar um algoritmo de tempo polinomial para um problema NP-completo.

III. Provar que um problema é NP-completo não é uma forte evidência de sua não-polinomialidade.

Neste contexto, é correto o que se afirma em:

Escolha uma:
a.
II e III, apenas.

b.
I, II e III.

c.
III, apenas.

d.
II, apenas.

e.
I e II, apenas.

Answer 1

Resposta:

1 - NÃO É NP-DIFÍCIL

2 - Redutível / Polinomial

3 - NÃO É I,II

Explicação:

Corrigido pelo AVA

Answer 2

Resposta:

1 - NP-Completo forte

2 - redutível / polinomial

3 - II, apenas

Explicação:

Corrigido pelo AVA