NP-complet

Un problème est NP-complet lorsqu'il peut être résolu par une classe restreinte d’algorithmes de recherche de force brute et qu'il peut être utilisé pour simuler tout autre problème avec un algorithme similaire.

Plus précisément, chaque entrée au problème doit être associé à un ensemble de solutions de longueur polynomiale, dont la validité peut être testée rapidement (en polynôme t ime , par exemple) que la sortie pour toute entrée est « oui » si la solution set est non vide et "non" s'il est vide. La classe de complexité des problèmes de cette forme est appelée NP, abréviation de " temps polynomial non déterministe ".

On dit qu'un problème est NP-difficile si tout en NP peut être transformé en temps polynomial en un problème, et un problème est NP-complet s'il est à la fois dans NP et NP-difficile. Les problèmes NP-complets représentent les problèmes les plus difficiles en NP. Si tout problème NP-complet a un algorithme polynomial, tous les problèmes de NP le sont. L'ensemble des problèmes NP-complets est souvent désigné par NP-C ou NPC.

Bien qu'une solution à un problème NP-complet puisse être vérifiée "rapidement", il n'existe aucun moyen connu de trouver une solution rapidement. C'est-à- dire que le temps nécessaire pour résoudre le problème en utilisant n'importe quel algorithme couramment connu augmente rapidement avec la taille du problème. En conséquence, déterminer s’il est possible de résoudre rapidement ces problèmes, appelé problème P versus NP, est l’un des problèmes fondamentaux non résolus en informatique de nos jours.

Tandis qu'une méthode permettant de calculer les solutions aux problèmes NP-complets reste rapidement à découvrir, les informaticiens et les programmeurs rencontrent encore fréquemment des problèmes NP-complets. Les problèmes NP-complets sont souvent traités en utilisant des méthodes heuristiques et des algorithmes d'approximation.