Um problema computacional é dito NP-completo quando

Alternativa correta: B - sua solução não é garantida em tempo polinomial.

Vamos entender melhor o que significa um problema NP-completo. Em ciência da computação, um problema é classificado como NP-completo se, para qualquer solução proposta para esse problema, pode-se verificar sua correção em tempo polinomial, e se qualquer problema em NP pode ser reduzido a ele em tempo polinomial.

Para resolver essa questão, é necessário ter conhecimentos básicos sobre complexidade de algoritmos e classes de problemas em ciência da computação. Vamos analisar cada uma das alternativas:

Alternativa A: "a complexidade de tempo no caso médio é igual à complexidade do pior caso."
Esta afirmação está incorreta. A classificação de NP-completo não está relacionada à comparação entre o caso médio e o pior caso de um problema.

Alternativa B: "sua solução não é garantida em tempo polinomial."
Esta é a resposta correta. Um problema NP-completo é aquele para o qual ainda não se descobriu um algoritmo que resolve o problema em tempo polinomial, ou seja, um tempo que pode ser expresso como uma função polinomial do tamanho da entrada.

Alternativa C: "a completude do programa pode ser demonstrada matematicamente."
Esta opção está incorreta. A completude matemática de um programa não está relacionada à definição de problemas NP-completos.

Alternativa D: "a complexidade de tempo no pior caso é igual a O(n^k), para algum k."
Esta afirmação está incorreta. Se um problema tivesse complexidade de tempo no pior caso igual a O(n^k), ele seria resolvido em tempo polinomial, o que não é uma característica de problemas NP-completos.

Alternativa E: "o resultado obtido não pode ser otimizado."
Esta opção está incorreta. A definição de NP-completo não menciona a otimização dos resultados, mas sim a capacidade de resolver ou verificar a solução em tempo polinomial.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

P: Problemas que podem ser resolvidos e verificados em tempo polinomial.

NP: Problemas cujas soluções podem ser verificadas em tempo polinomial.

NP-Completo: Problemas mais difíceis dentro de NP, para os quais nenhuma solução polinomial foi encontrada (mas também não foi provado que não existe).