Terra Incognita
Mathématiques

P est-il égal à NP ?

Horizon lointain

Pourquoi c'est important

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

Questions liées

Sources

Pas encore relu par un spécialiste.

Dernière vérification: 2026-11-18

Historique de cette question

Retour à la carte →