La question est de savoir si tout problème dont la réponse est facile à vérifier est aussi facile à résoudre. Si c'est le cas, les transports pourraient être planifiés de façon optimale, pour déplacer personnes et marchandises plus vite et moins cher, mais la cryptographie à clé publique deviendrait impossible.
Ce qu'on sait
La question est posée depuis 1971. Si un problème est facile à vérifier, est-il aussi facile à résoudre ?
Ce qui bloque
On a prouvé que plusieurs grandes familles de techniques de preuve ne peuvent pas suffire.
Pistes en cours
Théorie géométrique de la complexité, bornes inférieures sur les circuits.
Sous-questions
Peut-on prouver qu'un problème donné explicitement exige des circuits booléens de taille plus que linéaire ? La meilleure borne inférieure connue n'est que d'environ 4n.
NP est-il différent de co-NP ? De façon équivalente, n'existe-t-il aucun système de preuve offrant des preuves courtes de toutes les tautologies ?
Quelles techniques de preuve peuvent franchir les barrières connues de la « relativisation » et des « preuves naturelles » ?