Os problemas da classe NP utilizam algoritmos de verificação em tempo polinomial. Uma classe polinomial tem complexidade de tempo p(n) em 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 têm a complexidade de tempo O(n). Em relação à análise de algoritmos NP, analise as seguintes afirmações: 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(n)], 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:

Análise da Questão

Alternativa B

Esta questão aborda conceitos fundamentais da Teoria da Complexidade Computacional, especificamente as classes P e NP e o funcionamento de algoritmos não determinísticos.

Para chegar à resposta correta, devemos analisar cada afirmação com base nas definições de complexidade e nos dados fornecidos no enunciado.

## Análise Detalhada das Afirmações

Afirmação I: Incorreta.

"A complexidade do problema do caixeiro viajante é O(c)..."

• O Problema do Caixeiro Viajante é um problema clássico NP-Completo.
• Dizer que sua complexidade é $O(c)$ (tempo constante) é matematicamente impossível. O tempo necessário cresce drasticamente conforme o número de cidades aumenta.
• Mesmo com algoritmos heurísticos, garantir o melhor resultado (ótimo global) exige um esforço computacional muito maior que constante.

Afirmação II: Correta (no contexto do enunciado).

"A complexidade do problema de coloração de grafos é O(P(n)), uma vez que a solução do problema se dá em tempo polinomial."

• O problema de Coloração de Grafos pertence à classe NP.
• Segundo o enunciado, algoritmos não determinísticos utilizam a função escolhe() com custo $O(1)$.
• Num computador não determinístico, podemos "adivinhar" a cor de cada vértice em tempo proporcional ao número de vértices. Se verificarmos se a coloração é válida em tempo polinomial, o problema é resolvido em tempo polinomial neste modelo. Por isso, a afirmação é aceita como correta neste contexto teórico.

Afirmação III: Incorreta.

"...não sendo necessário analisar (n-1)! possibilidades de rota; logo, a complexidade é O(c)."

• Esta afirmação contradiz a própria natureza do problema. O espaço de busca do Caixeiro Viajante envolve permutações, onde o número de rotas possíveis é fatorial ($(n-1)!$).
• Ignorar essa análise torna a solução incompleta ou inválida.
• A conclusão de que a complexidade seria constante ($O(c)$) é falsa, refutando novamente a lógica da afirmação.

Afirmação IV: Correta.

"O problema da mochila utiliza um algoritmo não determinístico, cuja complexidade de tempo do problema é O(n)..."

• O Problema da Mochila é outro problema NP-Completo.
• Aplicando a regra do enunciado: para resolver este problema num algoritmo não determinístico, precisamos decidir para cada um dos $n$ itens se ele entra ou não na mochila.
• São necessárias $n$ operações de escolha.
• Como cada escolha custa $O(1)$ (conforme o texto), o tempo total é $n \times O(1) = O(n)$.
• Logo, a complexidade é linear em relação ao número de itens no modelo não determinístico.

Conclusão

As afirmações I e III são falsas porque atribuem complexidade constante ($O(c)$) a problemas que exigem análise combinatória massiva. As afirmações II e IV são consistentes com a definição de algoritmos não determinísticos apresentada no enunciado, onde a "adivinhação" ocorre em tempo polinomial ou linear.

Portanto, estão corretas apenas as afirmações II e IV.

Alternativa B