Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P (Ver NP-completo para una definición precisa).