Resposta da Questão
Alternativa D - A assertiva I é uma proposição falsa, e a II é uma proposição verdadeira.
Explicação Didática
Esta questão aborda conceitos fundamentais de Teoria da Complexidade Computacional, especificamente sobre a classe NP e a distinção entre problemas tratáveis e intratáveis. Vamos analisar cada parte separadamente.
1. Análise da Assertiva 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 pelos seguintes motivos:
- Generalização Incorreta: A classe NP (Tempo Polinomial Não-Determinístico) inclui tanto problemas fáceis quanto difíceis. Todo problema que pode ser resolvido em tempo polinomial (Classe P) também pertence à classe NP. Para esses problemas, a melhor solução é polinomial, não exponencial.
- Conjectura vs. Teorema: Ainda não foi provado se $P = NP$ ou $P \neq NP$. Embora se acredite que $P \neq NP$ (e que problemas NP-completos exijam tempo exponencial), afirmar categoricamente que a exponencial é a "melhor solução" é tratar uma conjectura como um fato absoluto.
- Definição de Melhor: Mesmo para problemas NP-completos, a busca por algoritmos melhores (como programação dinâmica ou heurísticas) continua ativa. Dizer que $O(c^n)$ é a melhor solução ignora avanços potenciais ou algoritmos pseudo-polinomiais.
2. Análise da Assertiva 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 é VERDADEIRA:
- Definição de Intratabilidade: Na ciência da computação, um problema é considerado intratável (ou não tratável) quando não existe nenhum algoritmo conhecido capaz de resolvê-lo em tempo polinomial.
- Crescimento Exponencial: Algoritmos com complexidade exponencial $O(c^n)$ (onde $c > 1$) crescem tão rapidamente que se tornam inviáveis para tamanhos de entrada moderados. Por exemplo, para $n=100$, $2^{100}$ é um número maior que o número de átomos no universo observável.
- Classificação Padrão: Portanto, problemas cuja melhor solução conhecida é exponencial são classificados como não tratáveis.
Resumo Comparativo
| Característica | Assertiva I | Assertiva II |
|---|
| Conteúdo | Afirma que toda NP é exponencial | Define problemas exponenciais como não tratáveis |
| Status | ❌ Falsa (ignora problemas em P e a incerteza $P \times NP$) | ✅ Verdadeira (alinhada com a definição de intratabilidade) |
| Relação | Não justifica a II | É uma definição correta independente |
Conclusão: Como a primeira parte é falsa e a segunda é verdadeira, a alternativa correta é a D.