classe de complexité P

Imaginez un mot formé de n bits, que l’on parcourt de gauche à droite pour savoir s’il contient un nombre pair de 1. Le travail augmente au même rythme que la longueur du mot : deux fois plus de bits demandent au plus deux fois plus de lectures.

Ce problème appartient à la classe P. Pour chaque entrée, une procédure déterministe donne la bonne réponse, et son temps de calcul reste borné par un polynôme de la taille de cette entrée.

La classe P rassemble des problèmes de décision, c’est-à-dire des familles de questions dont la réponse est oui ou non. Un problème est dans P lorsqu’il existe un algorithme déterministe correct qui le résout en temps polynomial pour toute entrée. « Déterministe » signifie qu’à chaque étape, l’état courant et la donnée lue imposent l’étape suivante.

On note n la taille de l’entrée et T(n) le nombre maximal d’étapes sur les entrées de cette taille. La borne polynomiale signifie qu’il existe des constantes c et k positives telles que, à partir d’une certaine taille :Le degré k et le facteur c dépendent de l’algorithme, mais pas de l’entrée particulière. Une borne linéaire ou quadratique est donc polynomiale, contrairement à une croissance exponentielle.

La thèse de Cobham fait du temps polynomial un critère théorique d’efficacité algorithmique. Ce critère ne garantit pourtant pas qu’un programme soit rapide sur des données réelles. Enfin, P est incluse dans NP : toute réponse calculable en temps polynomial est aussi vérifiable en temps polynomial. Savoir si P et NP sont égales demeure une question ouverte.

Le problème consiste à décider si un mot binaire contient un nombre pair de 1. L’entrée choisie est 10110100 : elle comporte n = 8 bits. L’algorithme conserve un état « pair » ou « impair », initialement pair.

1. Lire les bits de gauche à droite, une seule fois.

2. À chaque 1, basculer l’état de pair à impair, ou d’impair à pair. Un 0 laisse l’état inchangé. Pour 10110100, les états successifs sont impair, impair, pair, impair, impair, pair, pair, pair.

3. Après le huitième bit, répondre oui, car l’état final est pair. Le mot contient bien quatre 1.

Le contrôle consiste à recompter les quatre positions portant 1. Pour un mot de longueur n, l’algorithme lit exactement n bits : son temps est linéaire, donc polynomial. La succession des états permet de vérifier chaque bascule sans refaire tout le raisonnement.

Pour classer un problème de décision dans P, on décrit un algorithme déterministe, on prouve sa correction, puis on majore son pire temps d’exécution en fonction de la taille de l’entrée. Une simple mesure sur quelques essais ne remplace pas cette preuve.

Pour comparer deux algorithmes polynomiaux, l’appartenance à P ne suffit plus. Le degré du polynôme, les constantes cachées, la mémoire consommée et la taille habituelle des entrées déterminent lequel convient réellement.

Lorsqu’une tâche demande une valeur optimale plutôt qu’un oui ou un non, on formule souvent une question seuil : « existe-t-il une solution de valeur au moins donnée ? » Il faut ensuite établir séparément le lien entre cette version décisionnelle et la tâche initiale.

P et un algorithme polynomial. P est une classe de problèmes de décision ; l’existence d’un algorithme déterministe correct dont le temps d’exécution est polynomial établit l’appartenance d’un problème à cette classe. Plusieurs algorithmes de coûts différents peuvent résoudre le même problème.

P et NP. Dans P, une réponse peut être calculée en temps polynomial par un algorithme déterministe. Dans NP, toute réponse positive admet un certificat de taille polynomiale en celle de l’entrée, vérifiable en temps polynomial en la taille de l’entrée et du certificat. On sait que P est incluse dans NP, sans savoir si l’inclusion est stricte.

Temps polynomial et temps exponentiel. Une borne comme n³ reste polynomiale : l’exposant est fixe. Une borne comme 2ⁿ est exponentielle, car l’entrée n apparaît dans l’exposant. Doubler n fait nettement apparaître la différence.

La taille dépend du codage. Un entier écrit en binaire occupe beaucoup moins de symboles que le même entier écrit en unaire. Il faut donc annoncer l’encodage avant d’affirmer qu’un temps est polynomial en la taille de l’entrée.

P ne signifie pas instantané. Un temps en n¹⁰⁰ est polynomial, mais peut être inutilisable selon les constantes, la machine et les tailles d’entrée considérées. Le symptôme est un temps réel prohibitif malgré la classification ; il faut alors examiner le degré, les constantes et les données rencontrées.

La garantie porte sur le pire cas. Une exécution souvent rapide ne suffit pas si certaines entrées de taille n échappent à toute borne polynomiale démontrée. Il faut majorer le maximum sur toutes les entrées de cette taille.

Le problème doit être fixé. Un algorithme rapide sur quelques tailles ou instances ne classe pas à lui seul toute la famille. La preuve doit couvrir chaque taille et produire toujours une réponse correcte.

Temps polynomial précise la forme des bornes qui servent à reconnaître les algorithmes associés à P.

Complexité temporelle montre comment exprimer le nombre d’étapes en fonction de la taille de l’entrée.

Algorithme revient sur la procédure déterministe dont l’existence permet d’établir l’appartenance à P.

NP approfondit la classe qui contient P et situe la question encore ouverte de leur égalité.