Question

Os problemas que fazer parte da classe de complexidade P contém muitos problemas considrados problemas naturais, como programação linear. Forma a classe de complexidade fundamental, representado um conjunto de problemas de decisão.

Considerando o contexto, analise as afirmativas.

I. Problemas que fazem parte da classe P são problemas que podem ser resolvidos em tempo polinomial, por uma máquina de Turing não determinística.

II. Para um problema da classe P, com execução em tempo O(nk), o tamanho de k é irrelevante.

III. Problemas não p são mais difíceis de resolver que os problemas polinomiais.

Considerando o contexto, assinale a alternativa correta.
Escolha uma:

a. As afirmativas I, II e III estão corretas.

b. Apenas a afirmativa III está correta.

c. Apenas a afirmativa I está correta.

d. Apenas as afirmativas II e III estão corretas.

e. Apenas as afirmativas I e II estão corretas.

Answer 1

Resposta:

As afirmativas I, II e III estão corretas. Correto

Explicação:

Corrigido pelo AVA

Answer 2

Resposta:

a.

As afirmativas I, II e III estão corretas.