Question

1-Problemas NP-completo são estudados porque a habilidade de rapidamente verificar soluções para um problema (NP) parece correlacionar-se com a capacidade de resolver rapidamente esse problema (P).

Assinale a alternativa que apresenta corretamente um problema considerado NP-completo.

Escolha uma:
a.
Problema de Klening

b.
Problema do campo minado

c.
Problema da satisfatibilidade

d.
Problema da localização

e.
Problema da ordenação

2-Um avanço importante na questão P versus NP veio no início dos anos 1970s com o trabalho de Stephen Cook e Leonid Levin. Eles descobriram certos problemas em NP cuja complexidade individual está relacionada àquela da classe inteira. Se um algoritmo de tempo polinomial existe para quaisquer desses problemas, todos os problemas em NP seriam ____________ em tempo ____________. Esses problemas são chamados NP-completos.

Assinale a alternativa que preenche corretamente as lacunas.

Escolha uma:
a.
solúveis / exponencial

b.
solúveis / polinomial

c.
insolúveis / polinomial

d.
insolúveis / recursivo

e.
parcialmente solúveis / exponencial

3- Na teoria da complexidade computacional, um algoritmo numérico é executado em tempo ____________ se o seu tempo de execução é polinomial no valor numérico da entrada, mas é exponencial no comprimento da entrada – o número de bits necessários para representá-lo.

Assinale a alternativa que preenche corretamente a lacuna.

Escolha uma:
a.
Enumerável

b.
Recursivo

c.
Exponencial

d.
Polinomial

e.
Pseudopolinomial

Answer 1

Resposta:

1- Problema de satisfatibilidade;

2- Solúveis/ Polinomial;

3- Pseudopolinomial

Explicação:

CORRIGIDO PELO AVA.

Answer 2

Resposta:

1 -

2 -

3 -

Explicação: