Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto "S" de enteros, ¿existe un subconjunto no vacío de "S" cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2""-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.