Um problema computacional é dito NP-completo quando

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

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

a completude do programa pode ser demonstrada matematicamente.

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

o resultado obtido não pode ser otimizado.