$$\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

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 polynômial si, pour tout n, pour des données ne prenant pas plus de n octets, l'algorithme s'exécute en moins de C.nk 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 polynômiaux 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 polynômial.
  • 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 polynômial.
  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 polynômial 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 p1,...,pk, il est trivial de vérifier si n=p1...pk : 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 polynômial 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 polynômial, tandis qu'être dans NP, c'est prouver en temps polynômial 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 des mathématiques actuelles est l'investigation de la réciproque : a-t-on P=NP? Autrement dit, peut-on trouver en temps polynômial ce que l'on peut prouver en temps polynômial? 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 polynômial entraîne la résolution en temps polynômial 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...