NP-completude
Gabarito: letra B. Um problema é dito NP-completo quando, mesmo pertencendo à classe NP, não se conhece algoritmo determinístico que o resolva em tempo polinomial. Isso significa que sua solução não é garantida em tempo polinomial a menos que se prove que P = NP, o que até hoje não foi demonstrado.
A questão testa a definição formal de NP-completude, distinguindo-a de outros conceitos de complexidade, como casos médio/pior caso e complexidade polinomial.
Alternativa A — ❌ Incorreta
Afirma que a complexidade do caso médio é igual à do pior caso. Isso não define NP-completude; é uma caracterização possível para alguns algoritmos, mas não uma propriedade da classe NP-completo.
Alternativa B — ✅ Correta ⟵ GABARITO
Corresponde exatamente à definição: problemas NP-completos não possuem algoritmo polinomial conhecido; portanto, não se garante solução em tempo polinomial. Se houver um algoritmo polinomial para um NP-completo, todos os problemas em NP podem ser resolvidos em tempo polinomial (P = NP).
Alternativa C — ❌ Incorreta
"Completude do programa" não é um termo técnico associado a NP-completude. A demonstração matemática de corretude é uma prática de verificação, não uma definição da classe de complexidade.
Alternativa D — ❌ Incorreta
O(n^k) com constante k é tempo polinomial. Problemas NP-completos são justamente aqueles para os quais não se conhece algoritmo polinomial; se tivessem complexidade O(n^k), estariam em P. Alternativa inverte o conceito.
Alternativa E — ❌ Incorreta
A possibilidade de otimização não é critério para classificar um problema como NP-completo. Muitos problemas NP-completos podem ter soluções aproximadas ou heurísticas, mas isso não os define.
Gabarito: letra B.