Accueil |

Théorie de la complexité

   

La théorie de la complexité permet d'étudier de manière formelle la difficulté des problèmes en informatique.

En théorie de la complexité un problème est formalisé de la manière suivante : un ensemble de donnée en entrée, et une question sur ces données (et éventuelement un calcul a effectuer). La théorie de la complexité ne traite que des problèmes de décision, c.-à -d. des problèmes qui posent une question et dont la réponse est soit oui, soit non. L'ensemble des instances d'un problème est l'ensemble des données que peut prendre ce problème en entré. Une solution pour un problème est une structure représentable sur ordinateur qui est totalement indépendante du problème, par exemple l'ensemble des permutations sur n entiers.

On distingue essentielment ces trois classes de complexité :

On a .

Problème NP-Complet : Un problème est NP-Complet si il est dans NP, et si n'importe quel problème NP-Complet peut se réécrire à  l'aide d'un algorithme polynomial comme un sous ensemble d'instance de ce problème.

De manière plus intuitive, dire qu'un problème peut être décidé à  l'aide d'un algorithme non-déterminsite polynomial, signifie qu'il est facile pour une solution donné de vérifier en un temps polynomial si celle-ci répond au problème pour une instance donné (à  l'aide d'un Certificat); mais que le nombre de solutions à  tester pour réssoudre le problème est exponentiel par rapport à  la taille de l'instance. Le non-déterminisme permet de masquer la taille exponentiel des solutions à  tester tout en permetant à  l'algorithme de rester polynomial.

Jusqu'à  présent, il a été impossible de montrer qu'il existait des problèmes qui soient dans NP et non dans P. On conjecture cependant que les problèmes NP-complets ne sont pas résolubles en temps polynomial. La question "P = NP ?" est une des questions les plus fondamentales en informatique théorique depuis qu'elle a été posée en 1970. En effet, si il s'avérait que P = NP, alors on pourrait résoudre tous les problèmes en un temps polynomial; or les problèmes NP-Complets se retrouvent très fréquemment et pour aucun d'eux on n'a réussi à  trouver un algorithme polynomial le résolvant. Résoudre un problème NP-complet de manière exacte et en toute généralité, pour des entrées un tant soit peu grosses, demande un temps de calcul irréaliste par rapport au moyens informatiques dont nous disposons et même dont nous disposerons dans le futur prévisible. Des algorithmes d'optimisation permettent de trouver des solutions approchées de l'optimum en un temps raisonnable pour un certain nombre de programmes.

Le problème de démontrer que P et NP sont distinctes attire une attention considérable, et un prix Clay de 1000000$ sera offert à  celui qui le résoudra.

Problème NP-Complets célèbres: