Théorie des bornes inférieures en complexité algorithmique

Cet article traite de la théorie des bornes inférieures en complexité algorithmique, un domaine fondamental en informatique théorique. Il s'adresse aux étudiants et chercheurs souhaitant comprendre comment évaluer la difficulté intrinsèque des problèmes algorithmiques, déterminer l'efficacité optimale des algorithmes, et appréhender la classification des problèmes selon leur complexité. Cette introduction offre une base claire pour aborder les concepts clés de la complexité, les classes P, NP, NP-complet, ainsi que les méthodes de preuve et les implications pratiques.

La question

Le travail s'intéresse à la question suivante : comment déterminer la complexité minimale nécessaire pour résoudre un problème algorithmique donné ? Plus précisément, il s'agit de montrer qu'un algorithme est optimal en établissant une borne inférieure sur le nombre d'opérations nécessaires dans le pire cas. Cette question est cruciale car elle permet de savoir si un algorithme peut être amélioré ou si la complexité actuelle est la meilleure possible. Cela oriente aussi la recherche vers des approches alternatives lorsque le problème est intrinsèquement difficile.

Concepts de base

Avant de comprendre les résultats, il est essentiel de maîtriser plusieurs notions fondamentales :

• Complexité d’un algorithme : mesure du nombre d’opérations nécessaires en fonction de la taille de l’entrée, souvent exprimée en notation asymptotique (Θ, O, Ω).
• Borne inférieure : un seuil minimal sur la complexité que tout algorithme doit respecter pour résoudre un problème.
• Arbres de décision : structures binaires représentant les comparaisons effectuées par un algorithme, où la profondeur maximale correspond au nombre maximal de comparaisons.
• Classes de complexité : classification des problèmes selon la difficulté de leur résolution, notamment les classes P (problèmes résolubles en temps polynomial) et NP (problèmes dont les solutions peuvent être vérifiées en temps polynomial).
• Problèmes NP-complets : problèmes dans NP qui sont au moins aussi difficiles que tous les autres problèmes de NP, au sens où tout problème NP peut être réduit en temps polynomial à un problème NP-complet.
• Réduction polynomiale : transformation d’un problème en un autre en temps polynomial, conservant la réponse correcte, utilisée pour comparer la difficulté des problèmes.
• Problèmes de décision : problèmes dont la réponse est toujours "oui" ou "non", souvent utilisés pour formaliser les questions de complexité.
• Heuristiques et algorithmes approximatifs : méthodes pour obtenir des solutions acceptables en temps raisonnable lorsque le problème est trop difficile à résoudre exactement.

Approche

La méthode principale consiste à établir des bornes inférieures sur la complexité des problèmes en utilisant des arguments combinatoires et des structures comme les arbres de décision. Par exemple, pour le tri par comparaisons, on montre que le nombre minimal de comparaisons est lié au logarithme factoriel du nombre d’éléments à trier, soit Ω(n log n). Cette borne est démontrée en analysant le nombre de permutations possibles et en utilisant la propriété que la profondeur d’un arbre binaire avec k feuilles est au moins log k.

Pour les problèmes plus complexes, notamment ceux de la classe NP, la théorie utilise la notion de réduction polynomiale pour montrer que certains problèmes sont aussi difficiles les uns que les autres. La preuve qu’un problème est NP-complet passe par :

• Montrer qu’il appartient à NP (vérification en temps polynomial d’une solution proposée).
• Réduire un problème déjà connu NP-complet à ce problème via une transformation polynomiale.

Cette approche est illustrée par la réduction du problème 3-SAT (satisfiabilité d’une formule booléenne en forme normale conjonctive avec 3 littéraux par clause) au problème CLIQUE (existence d’une clique de taille k dans un graphe). Cette réduction montre que résoudre CLIQUE est au moins aussi difficile que résoudre 3-SAT, prouvant ainsi que CLIQUE est NP-complet.

Enfin, face à la difficulté des problèmes NP-complets, deux stratégies sont proposées :

• Améliorer la recherche exhaustive tout en acceptant une complexité exponentielle.
• Utiliser des heuristiques ou algorithmes approximatifs qui fournissent des solutions proches de l’optimal en temps raisonnable.

Résultats

Plusieurs conclusions importantes émergent de cette étude :

• Il existe des bornes inférieures strictes pour des problèmes classiques, par exemple Ω(n log n) pour le tri par comparaisons, ce qui prouve que certains algorithmes comme le tri par fusion sont optimaux.
• La classe P regroupe les problèmes pour lesquels il existe des algorithmes déterministes en temps polynomial, tandis que NP regroupe ceux dont on peut vérifier une solution en temps polynomial.
• Les problèmes NP-complets sont les plus difficiles dans NP, car tout problème NP peut être réduit à eux.
• Si un seul problème NP-complet était résolu en temps polynomial, alors tous les problèmes NP seraient dans P, ce qui est considéré comme très improbable.
• Des problèmes classiques comme le problème du commis voyageur, la coloration de graphes, le problème du cycle hamiltonien, ou la clique sont NP-complets.
• Des méthodes d’approximation existent, comme l’algorithme 2-approximation pour le problème du commis voyageur avec inégalité triangulaire, garantissant une solution au plus deux fois plus coûteuse que l’optimum.

Limitations et questions ouvertes

Le travail souligne plusieurs limites et questions non résolues :

• La question centrale ouverte est de savoir si P = NP, c’est-à-dire si tous les problèmes dont la solution peut être vérifiée rapidement peuvent aussi être résolus rapidement. Cette question reste non résolue.
• Pour de nombreux problèmes NP-complets, aucun algorithme polynomial exact n’est connu, et il est probable qu’il n’en existe pas.
• Les heuristiques et algorithmes approximatifs ne garantissent pas toujours une bonne qualité de solution, et leur efficacité peut varier selon les instances.
• La théorie ne traite pas des problèmes non décidables, pour lesquels aucun algorithme ne peut exister (exemple : problème de l’arrêt).

Glossaire

• Algorithme polynomial : algorithme dont la complexité est bornée par un polynôme en la taille de l’entrée.
• Borne inférieure : limite minimale sur la complexité que tout algorithme doit respecter pour un problème donné.
• Classe P : ensemble des problèmes de décision résolubles en temps polynomial par un algorithme déterministe.
• Classe NP : ensemble des problèmes de décision pour lesquels une solution proposée peut être vérifiée en temps polynomial.
• NP-complet : problème dans NP auquel tout autre problème NP peut être réduit en temps polynomial, représentant les problèmes les plus difficiles de NP.
• Réduction polynomiale : transformation d’un problème en un autre en temps polynomial, conservant la réponse correcte.
• Problème de décision : problème dont la réponse est "oui" ou "non".
• Heuristique : méthode algorithmique visant à trouver une solution acceptable rapidement, sans garantie d’optimalité.
• Forme normale conjonctive (FNC) : expression booléenne composée d’une conjonction de clauses, chaque clause étant une disjonction de littéraux.
• Cycle hamiltonien : cycle passant une seule fois par chaque sommet d’un graphe.
• Cliques : sous-ensemble de sommets d’un graphe où chaque paire de sommets est reliée par une arête.
• Inégalité triangulaire : propriété des poids dans un graphe pondéré, w(a,b) + w(b,c) ≥ w(a,c).
• Arbre recouvrant minimal (MST) : arbre couvrant tous les sommets d’un graphe avec un poids total minimal.