← Unknownpedia : voir sur la carte

Vérifier une solution est-il aussi difficile que la trouver ?

C'est le problème « P contre NP », la question centrale de la théorie de la complexité.

Brouillon rédigé avec une IA (Claude). Les références existent, vérifiées dans OpenAlex ; le texte n’a pas encore été relu par un spécialiste. Qui écrit quoi

Ce qu'on sait

Ce qu'on ignore

Pourquoi c'est dur

Pourquoi ça compte

Si P était égal à NP avec un algorithme pratique, une grande partie de la cryptographie actuelle serait cassée. Dans l'autre cas, on saurait que pour des milliers de problèmes, aucune astuce ne donnera d'algorithme rapide.

Par où commencer

Pour aller plus loin

Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable.

Extrait de l'article Wikipédia « Problème P ≟ NP » (licence CC BY-SA).