Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Théorie de la complexité

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

Généralités

En théorie de la complexité, un problème est formalisé de la manière suivante : un ensemble de données en entrée, et une question sur ces données (pouvant demander éventuellement un calcul). La théorie de la complexité ne traite que des problèmes de décision binaire, c'est-à-dire posant une question dont la réponse soit oui ou non.

On considère que l'ensemble des instances d'un problème est l'ensemble des données que peut accepter ce problème en entrée, par exemple l'ensemble des permutations de n entiers à trier pour un algorithme de tri.

On distingue des classes de complexité :

• Classe P : un problème de décision est dans P s'il peut être décidé par un algorithme déterministe en un temps polynomial par rapport à la taille de l'instance. On qualifie alors le problème de polynomial.
• Classe NP : c'est la classe des problèmes de décision pour lesquels la réponse oui peut être décidée par un algorithme non-déterministe en un temps polynomial par rapport à la taille de l'instance.
• Classe Co-NP : nom parfois donné pour l'équivalent de la classe NP avec la réponse non.

On a .

Problème NP-Complet

Un problème est NP-Complet s'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éterministe polynomial, signifie qu'il est facile, pour une solution donnée, de vérifier en un temps polynomial si celle-ci répond au problème pour une instance donnée (à l'aide d'un Certificat); mais que le nombre de solutions à tester pour résoudre le problème est exponentiel par rapport à la taille de l'instance. Le non-déterminisme permet de masquer la taille exponentielle des solutions à tester tout en permettant à 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 solubles en un 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, s'il s'avérait que P = NP, alors on pourrait résoudre tous les problèmes NP en un temps polynomial sur une machine déterministe; 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 aux moyens informatiques dont nous disposons et même dont nous disposerons dans un 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.

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

• Problème SAT et variante 3SAT
• Problème du voyageur de commerce
• Problème du cycle hamiltonien
• Problème de la clique maximum
• Problèmes de colorations de graphes

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