Question

A análise de complexidade provê critérios para a classificaçãode problemas com base na computabilidade de suas soluções,utilizando-se a máquina de Turing como modelo referencial epossibilitando o agrupamento de problemas em classes. Nessecontexto, julgue os itens a seguir.I É possível demonstrar que P f NP e NP f P.II É possível demonstrar que se P NP, entãoP 1 NP-Completo = i.III Se um problema Q é NP-difícil e Q 0 NP, então Q éNP-completo.IV O problema da satisfatibilidade de uma fórmula booleana F(uma fórmula é satisfatível, se é verdadeira em algummodelo) foi provado ser NP-difícil e NP-Completo.V Encontrar o caminho mais curto entre dois vértices dadosem um grafo de N vértices e M arestas não é um problemada classe P.Estão certos apenas os itensA I, III e IV.B II, III, e IV.C III, IV e V.D I, II, III, e IV.E II, III, IV e V

#ENADE

Answer 1

A alternativa correta é a B II, III, e IV.

As máquinas resolvem computadores em quantidade razoável de tempo. Quando isso acontece os problemas são conhecidos como polinomiais. Com isso se agrupa os polinomiais e se chamando de classe P.

Eles são conhecidos por seu tempo de cálculo no qual se descreve um polinômio em relação aos dados. Como a questão de multiplicar em suas duas matrizes de n. Outra classe de problemas é conhecida como NP com um conceito de dado por tal maneira.

Espero ter ajudado.