$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Applications > Algorithmique >
Dictionnaire de mathématiques > Histoire > Problèmes célèbres > Problèmes du millénaire >

Classes de complexité

Certains problèmes sont plus difficiles que d'autres. Par exemple, étant donné un nombre, il est très facile de tester si ce nombre est divisible par 2 ou non : il suffit de regarder si le dernier chiffre appartient à l'ensemble {0,2,4,6,8}. En revanche, il est beaucoup plus difficile de déterminer sa décomposition en produits de facteurs premiers.

Définition : Un algorithme est dit en temps polynomial si, pour tout entier $n$, pour des données ne prenant pas plus de $n$ octets, l'algorithme s'exécute en moins de $C\times n^k$ opérations élémentaires (les constantes $C$ et $k$ étant bien sûr indépendantes de $n$).

Dans la définition précédente, le terme d'opérations élémentaires est assez vague. On doit le comprendre comme des additions, des multiplications, des comparaisons, etc... (tout ce que le processeur sait réaliser en un temps fixe). Ce qu'il faut retenir, c'est que les algorithmes polynomiaux sont les seuls à pouvoir être utilisés informatiquement pour de grandes valeurs de $n$, et ce, quelle que soit la puissance de la machine.

Définition :
  • On dit qu'un problème est dans P s'il existe un algorithme pour le résoudre en temps polynomial.
  • On dit qu'un problème est dans NP s'il existe un algorithme pour vérifier qu'une solution donnée convient en un temps polynomial.

La définition d'un problème NP peut sembler complexe. Essayons de l'éclaicir. Un des problèmes difficiles des mathématiques est la factorisation d'un entier en produit de facteurs premiers. On ne sait pas s'il existe un algorithme polynomial qui réussisse cette opération. Autrement dit, on ne sait pas si ce problème est dans P. En revanche, étant donné des nombres $p_1,\dots,p_k$, il est trivial de vérifier si $n=p_1\cdots p_k$ : ce problème est dans NP.

Un autre problème classique est celui du voyageur de commerce. Ce voyageur doit visiter $n$ villes pour vendre sa camelote. Il existe entre ces villes un certain nombre de routes. Existe-t-il un trajet permettant de visiter toutes les villes en moins de $b$ kms. C'est un problème difficile, et on ne sait pas s'il existe un algorithme polynomial pour le résoudre. En revanche, si l'on donne un trajet, il est quasi-immédiat de vérifier si ce trajet fait moins de $b$ kms. Le problème est dans NP.

Pour résumer, être dans P, c'est trouver une solution en temps polynomial, tandis qu'être dans NP, c'est vérifier en temps polynomial qu'une proposition de réponse est une solution du problème. Ainsi, tout problème qui est dans P se trouve dans NP. Un champ de recherche majeur, à l'interface entre les mathématiques et l'informatique, est l'étude de la réciproque : a-t-on P=NP? Autrement dit, peut-on trouver en temps polynomial ce que l'on peut vérifier en temps polynomial? Ce problème est si important qu'il fait partie des 7 problèmes du millénaire, dont la résolution est primée 1 million de dollars par le Clay Mathematic Institute.

Définition : On dit qu'un problème est NP-complet si la résolution de ce problème en temps polynomial entraîne la résolution en temps polynomial de tout problème NP.

Les problèmes NP-complets sont donc les plus compliqués des problèmes NP. On peut aller jusqu'à douter de leur existence. Pourtant, on sait depuis 1970 qu'il en existe. Le problème du voyageur de commerce en est un. Celui du sac à dos un autre.

Consulter aussi
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives