Um problema computacional é dito NP-completo quando

a) a complexidade de tempo no caso médio é igual à complexidade do pior caso.

b) sua solução não é garantida em tempo polinomial.

c) a completude do programa pode ser demonstrada matematicamente.

d) a complexidade de tempo no pior caso é igual a O(n^k), para algum k.

e) o resultado obtido não pode ser otimizado.

Responda: Um problema computacional é dito NP-completo quando