Pregunta si todo problema cuya respuesta es fácil de comprobar también es fácil de resolver. Si es así, el transporte podría planificarse de forma óptima, moviendo personas y mercancías más rápido y más barato, pero la criptografía de clave pública sería imposible.
Lo que sabemos
Planteado en 1971: si un problema es fácil de comprobar, ¿es también fácil de resolver?
Lo que nos frena
Se ha demostrado que varias grandes familias de técnicas de demostración son insuficientes.
Pistas actuales
Teoría de la complejidad geométrica, cotas inferiores para circuitos.
Subpreguntas
¿Puede alguien demostrar que algún problema dado explícitamente necesita circuitos booleanos de tamaño mayor que lineal? La mejor cota inferior conocida es solo de unos 4n.
¿Es NP distinto de co-NP? De forma equivalente, ¿no existe ningún sistema de prueba con demostraciones cortas de todas las tautologías?
¿Qué técnicas de demostración pueden superar las barreras conocidas de la «relativización» y las «pruebas naturales»?