Temps polynomial

Imaginez une liste de codes et un programme qui compare chaque paire pour repérer un doublon. Avec 6 codes, il effectue 15 comparaisons ; avec 8 codes, 28. Le travail augmente vite, mais selon une règle quadratique liée au carré de la taille de la liste.

Un temps est dit polynomial lorsque, pour les grandes entrées, une puissance fixe de leur taille suffit à borner le nombre d'étapes. Cette garantie décrit la croissance du calcul, pas sa durée exacte sur un ordinateur donné.

La taille de l'entrée, notée n, mesure la longueur de son encodage. Le temps d'exécution T(n) désigne ici le nombre maximal d'étapes, parmi toutes les entrées de taille n, dans un modèle de calcul fixé. Il est polynomial s'il existe une constante positive c, un entier k ≥ 0 et un seuil n₀ tels que $T(n)\le c{n}^{k}T(n)\; \backslash le\; c\; n^k$ pour toute taille n ≥ n₀. L'exposant k et la constante c sont fixes : ils ne dépendent pas de l'entrée. On note alors T(n) = O(n^k).

Cette propriété s'applique à un algorithme, relativement à un encodage et à un modèle raisonnables. La classe P rassemble les problèmes de décision, c'est-à-dire les questions dont la réponse est oui ou non, qu'un algorithme déterministe résout en temps polynomial. La classe NP rassemble les problèmes de décision pour lesquels une réponse oui accompagnée d'un certificat de longueur polynomiale peut être vérifiée en temps polynomial.

Tout problème de P appartient à NP, car une solution calculable rapidement est aussi vérifiable rapidement. On ignore en revanche si tout problème de NP appartient à P : c'est la question P = NP. Un temps polynomial est donc une notion asymptotique de complexité, et non une promesse qu'un programme sera rapide sur chaque taille concrète.

Un programme cherche un doublon parmi 6 codes tous distincts. Il compare chaque paire une fois et s'arrête après avoir épuisé les paires. Les données sont donc une liste de taille n = 6 et une comparaison pour chaque choix de deux positions.

1. Le premier code est comparé aux 5 suivants.
2. Le deuxième ajoute 4 comparaisons nouvelles.
3. Les codes suivants en ajoutent 3, puis 2, puis 1.
4. Le total vaut 5 + 4 + 3 + 2 + 1 = 15 comparaisons.

Pour une taille générale n, le nombre C(n) de comparaisons est $C(n)=\frac{n(n-1)}{2}C(n)=\backslash frac\{n(n-1)\}\{2\}$. Ce polynôme de degré 2 est borné par n²/2 pour toute taille positive. Si une comparaison coûte un nombre constant d'étapes, l'algorithme s'exécute donc en temps O(n²).

Le contrôle se refait avec 8 codes : 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28, ce qui coïncide avec 8 × 7 / 2. Le résultat compte les comparaisons dans le pire cas sans doublon ; une rencontre plus précoce peut interrompre le programme avant ce total.

Lorsqu'on étudie un algorithme, on choisit d'abord ce qui mesure la taille de l'entrée, puis on compte ses opérations dominantes. Pour la recherche naïve de doublons, compter les paires révèle une croissance quadratique ; examiner seulement quelques chronométrages ne suffit pas à l'établir.

Pour chercher un doublon sans examiner toutes les paires, on peut trier les codes puis comparer leurs voisins. Cette alternative devient préférable quand la liste grandit et que le tri évite le nombre quadratique de comparaisons ; le coût du tri et la mémoire disponible départagent les cas concrets.

En complexité, on reformule souvent une optimisation en problème de décision. Pour le voyageur de commerce, on demande alors s'il existe une tournée dont la longueur ne dépasse pas une borne donnée, au lieu de demander directement la plus courte tournée. Cette forme oui-non permet de parler précisément des classes P et NP.

Temps polynomial et classe P. Le premier qualifie l'exécution d'un algorithme ; la seconde classe des problèmes de décision qui possèdent un algorithme déterministe polynomial. Un même problème peut avoir un algorithme lent et appartenir malgré tout à P grâce à un autre algorithme polynomial.

P et NP. P porte sur la résolution déterministe en temps polynomial. NP porte sur la vérification polynomiale d'un certificat pour une réponse oui. Un problème résolu en temps polynomial appartient aux deux classes ; on ignore si les deux classes sont égales.

NP et NP-complet. NP contient tous les problèmes de décision dont les certificats oui se vérifient en temps polynomial. Un problème NP-complet appartient à NP et tout problème de NP se réduit à lui en temps polynomial. Être dans NP ne suffit donc pas à être NP-complet.

La taille est celle de l'encodage. Un entier écrit en binaire avec n bits peut atteindre 2ⁿ − 1. Compter un nombre d'étapes polynomial dans sa valeur numérique ne garantit donc pas un temps polynomial dans la longueur réellement fournie. Il faut annoncer l'encodage avant de conclure.

Polynomial ne signifie pas automatiquement rapide. Une borne n¹⁰⁰ est polynomiale, tandis qu'une petite instance d'un algorithme exponentiel peut finir aussitôt. Le classement porte sur la croissance asymptotique ; pour une utilisation réelle, il faut aussi examiner le degré, les constantes et les tailles rencontrées.

Pour établir directement une borne polynomiale, l'exposant doit rester fixe. Si une majoration de la forme n^k(n) a un exposant qui croît avec n, elle ne suffit pas à prouver que le temps est polynomial. Elle ne démontre pas non plus, à elle seule, qu'il ne l'est pas : une majoration peut être trop lâche. Remplacer k par n donne ainsi nⁿ, qui n'est pas une borne polynomiale.

Le cas compté doit être précisé. Le détecteur de doublons peut s'arrêter tôt, mais il effectue 15 comparaisons sur 6 codes distincts. Une mesure favorable ne remplace pas la borne du pire cas utilisée pour établir son temps quadratique.

algorithme — Pour replacer le temps d'exécution parmi les propriétés d'une procédure finie et explicite.

NP — Pour approfondir la vérification par certificat et sa relation avec la question P = NP.

problème du voyageur de commerce — Pour étudier un problème concret où décision, optimisation et complexité doivent être distinguées.