Os problemas da classe NP utilizam algoritmos de verificação em tempo polinomial. Uma classe polinomial tem complexidade de tempo O(p(n)), em que p...

Os problemas da classe NP utilizam algoritmos de verificação em tempo polinomial. Uma classe polinomial tem complexidade de tempo O(p(n)), em que p(n) é um polinômio e n é o tamanho da entrada. Além disso, a classe NP utiliza algoritmos não determinísticos que usam a função escolhe (X) com a complexidade de tempo O(1) e os comandos sucesso e insucesso também com a complexidade de tempo O(1). Em relação à análise de algoritmo dos problemas NP, analise as seguintes afirmações: I. A complexidade do problema do caixeiro viajante é O(c), e a solução encontrada obteve o melhor resultado. II. A complexidade do problema de coloração de grafos é O(P(x)), uma vez que a solução do problema se dá em tempo polinomial. III. O objetivo do problema do caixeiro viajante é percorrer a rota de menor custo, não sendo necessário analisar (n-1)! possibilidades de rota; logo, a complexidade é O(c). IV. O problema da mochila utiliza um algoritmo não determinístico, cuja complexidade de tempo do problema é O(n), sendo n o tamanho ​​​​​​​da entrada. Está correto o que se afirma em: A. I, II e III. B. II e IV. C. II e III. D. I, III e IV. E. I, II, III e IV.