P contre NP
Le problème ouvert le plus célèbre de l'informatique. Les problèmes dont la solution se vérifie vite (NP) se résolvent-ils aussi vite (P) ? La plupart pensent que non, mais aucune preuve. Prix du Millénaire d'un million de dollars.
Formulé par Stephen Cook (1971). Si P = NP, toute la cryptographie s'effondrerait (RSA, AES reposent sur des hypothèses de difficulté calculatoire). Problèmes NP-complets (voyageur de commerce, SAT, sac à dos) : en résoudre un rapidement revient à tous les résoudre. Conséquence pratique : on accepte que certains problèmes soient « difficiles » et l'on recourt à des heuristiques et à des approximations (recuit simulé, algorithmes génétiques, relaxation linéaire). L'informatique quantique ne déplace pas la frontière — BQP est une autre classe de complexité.