Question

1-Considere o problema de se testar se dois números são primos entre si, onde dois números são primos entre si se 1 é o maior inteiro que divide ambos.

Assinale a alternativa que apresenta corretamente a que classe de problemas pertence o problema mencionado.

Escolha uma:
a.
NPSPACE

b.
NP-completo

c.
Tempo exponencial

d.
Não-determinístico

e.
Tempo polinomial

2-Sobre a classe de problemas P marque as afirmativas a seguir com verdadeiras (V) ou falsas (F).

( ) P é conhecido por conter vários problemas naturais, incluindo as versões de decisão de Programação linear, o cálculo do Máximo divisor comum

( ) Uma linguagem está em P se ela é decidida por alguma máquina de Turing não-determinística de tempo polinomial.

( ) Quando um problema está em P, temos um método de resolvê-lo que roda em tempo nk para alguma constante k.

Assinale a alternativa que apresenta a sequência correta.

Escolha uma:
a.
V – F – V

b.
V – V - V

c.
F – V – V

d.
V – F – F

e.
F – V – F

3-A classe P dos problemas polinomiais consiste nos problemas de ____________ que, numa codificação razoável, podem ser resolvidos por algoritmos determinísticos em tempo ____________.

Assinale a alternativa que preenche corretamente as lacunas.

Escolha uma:
a.
decisão / polinomial

b.
Post / polinomial

c.
busca / não-polinomial

d.
decisão / não-polinomial

e.
decisão / exponencial

Answer 1

Resposta:

2 - V-F-V

3 - Decisão/polinomial

Explicação:

Corrigido pelo AVA

Answer 2

Resposta:

Resposta da Pergunta 1 (Considere o problema de se testar [...])

Tempo polinomial

Explicação:

Corrigido pelo AVA