Comprendre la complexité NP : définition et exemples

NP signifie « Temps polynomial non déterministe ». Il s'agit d'une classe de complexité qui fait référence au temps nécessaire pour résoudre un problème. Dans NP, le temps d'exécution d'un algorithme peut être polynomial en termes de taille de l'entrée, mais il peut également être non déterministe, ce qui signifie que le temps d'exécution peut varier en fonction de la solution spécifique choisie par l'algorithme.

En d'autres termes, NP est un classe de problèmes pouvant être résolus en temps polynomial sur une machine non déterministe. Une machine non déterministe est une machine capable d’essayer en parallèle toutes les solutions possibles à un problème et d’accepter la première qui fonctionne. Cela permet à la machine de résoudre certains problèmes beaucoup plus rapidement qu'une machine déterministe, qui ne peut essayer qu'une seule solution à la fois.

Quelques exemples de problèmes dans NP incluent :

* Le problème du voyageur de commerce (étant donné une liste de villes et leurs distances par paires, trouver l'itinéraire le plus court possible qui visite chaque ville exactement une fois)
* Le problème du sac à dos (étant donné un ensemble d'articles et leurs poids et valeurs, déterminer le sous-ensemble d'articles à inclure dans un sac à dos de capacité limitée qui maximise la valeur totale)
* Le problème de satisfiabilité booléenne (étant donné un ensemble de variables booléennes et leurs contraintes, déterminer s'il existe une attribution de valeurs aux variables qui satisfait toutes les contraintes)

La classe de complexité NP est importante car elle comprend de nombreux problèmes difficiles à résoudre en polynôme temps, mais peut être vérifié rapidement par une machine déterministe. Cela signifie que même si un algorithme n’est pas capable de trouver une solution en temps polynomial, il peut quand même être utile s’il peut vérifier rapidement une solution proposée.