Existe otra clase importante de problemas para los cuales no se conocen soluciones eficientes, pero no se ha logrado probar que no la tengan, y tienen la siguiente peculiaridad: los mejores algoritmos que se conocen corren en tiempo exponencial, pero se pueden verificar eficientemente. Estos problemas se denominan NP-completos.
Curiosidades
El matemático francés Édouard Lucas publicó el acertijo de las torres de Hanoi en 1883 bajo el seudónimo de M. Claus, en el cuarto volumen de Récréations mathématiques. Quizás se inspiró en un problema similar que apareció en la edición de De Subtilitate del matemático italiano Girolamo Cardano. En 1884, otro matemático francés, De Parville, asoció al juego de las torres de Hanoi la siguiente leyenda: "En el gran templo de Benarés, debajo del domo que indica el centro del mundo, se encuentra un plato de metal que tiene fijas tres torres con diamantes. Al crear el mundo, Dios colocó sesenta y cuatro discos de oro en la torre de Brahma. Los discos son de diferente tamaño e inicialmente fueron colocados en orden decreciente de diámetros. Día y noche los monjes tienen que trasladar los discos desde la primera torre a una de las otras dos. La única operación permitida es mover un disco de una torre a otra cualquiera, pero con la condición de que no se puede situar encima de un disco otro de diámetro mayor. La leyenda dice que cuando los monjes terminen su tarea, las torres, el templo y los brahamaneses se convertirán en polvo y, después de un trueno, el mundo desaparecerá."
Esto es, si alguien presenta una supuesta solución, se puede diseñar un algoritmo de tiempo polinomial que verifica si en efecto se trata de una solución al problema. El problema de Arcadio es justo de este tipo, si se toma en cuenta una pequeña variante.
Esta variante pide encontrar los regalos que tienen un valor emocional de al menos X unidades. Si Arcadio afirma que ya encontró una solución, por ejemplo, comprar el dije y los aretes por al menos 
15, simplemente se suman los valores del dije y de los aretes, se verifica que no exceda el dinero con el que cuenta, se suman sus valores emocionales y se comprueba que sea de al menos 15.
Una situación fascinante en computación son los cientos de problemas que las personas han encontrado en la práctica y tienen que resolver, aunque sean NP-completos. Para todos esos problemas no se conocen soluciones eficientes y no se sabe si existan. Ésta es la llamada pregunta P = NP.
