Analisar a complexidade de um problema computacional é definir o algoritmo que tem o melhor resultado em relação ao consumo de tempo em função do tamanho da sua entrada, no pior caso, na resolução de determinado problema. Porém, ainda não foram descobertos os melhores algoritmos para resolver muitos problemas computacionais. Avalie as seguintes asserções e a relação proposta entre elas: I. A complexidade assintótica de ordem exponencial – O(c^n) representa a melhor solução para os problemas da classe NP. II. Os algoritmos de complexidade O(c^n) são conhecidos como um problema não tratável se a solução para determinado problema contém o melhor resultado.

Alternativa D

Introdução

Esta questão aborda conceitos fundamentais da Teoria da Complexidade Computacional, especificamente sobre as classes P e NP, bem como a definição de problemas tratáveis e não tratáveis. Para responder corretamente, é necessário entender a hierarquia entre essas classes e o significado prático da complexidade exponencial.

Análise das Asserções

Vamos analisar cada afirmação separadamente para determinar sua veracidade:

• Asserção I: "A complexidade assintótica de ordem exponencial – $O(c^n)$ representa a melhor solução para os problemas da classe NP."
• Esta afirmação é FALSA.
• Motivo: A classe NP (Non-deterministic Polynomial time) engloba todos os problemas cujas soluções podem ser verificadas em tempo polinomial. Importantly, a classe P (polinomial) está contida dentro da classe NP ($P \subseteq NP$).
• Isso significa que existem muitos problemas em NP que podem ser resolvidos eficientemente em tempo polinomial (exemplo clássico: ordenação de dados, caminho mais curto em grafos). Portanto, afirmar que a melhor solução para todos os problemas da classe NP é exponencial ignora a existência dos problemas da classe P.
• Asserção II: "Os algoritmos de complexidade $O(c^n)$ são conhecidos como um problema não tratável se a solução para determinado problema contém o melhor resultado."
• Esta afirmação é considerada VERDADEIRA no contexto geral da teoria.
• Motivo: Na ciência da computação, problemas cuja solução exige tempo exponencial ($O(c^n)$, onde $c > 1$) são classificados como intratáveis (ou não tratáveis).
• O crescimento exponencial faz com que, mesmo para tamanhos de entrada moderados, o tempo de execução se torne impraticável. Embora a redação seja levemente informal ao associar o algoritmo diretamente ao problema, o conceito central de que tempo exponencial $\Rightarrow$ intratabilidade está correto.

Conclusão

Com base na análise técnica:

1. A Asserção I é Falsa (por ignorar a subclasse P dentro de NP).
2. A Asserção II é Verdadeira (pois associa corretamente complexidade exponencial à intratabilidade).

Portanto, a alternativa correta é a D.