Complexité temporelle - Time complexity

Graphiques des fonctions couramment utilisées dans l' analyse des algorithmes , montrant le nombre d'opérations N par rapport à la taille d'entrée n pour chaque fonction

En informatique , la complexité temporelle est la complexité de calcul qui décrit le temps qu'il faut à l'ordinateur pour exécuter un algorithme . La complexité temporelle est communément estimée en comptant le nombre d'opérations élémentaires effectuées par l'algorithme, en supposant que chaque opération élémentaire prend un temps fixe pour s'effectuer. Ainsi, le temps pris et le nombre d'opérations élémentaires effectuées par l'algorithme sont supposés être liés par un facteur constant .

Étant donné que le temps d'exécution d'un algorithme peut varier entre différentes entrées de même taille, on considère généralement la complexité temporelle dans le pire des cas , qui est le temps maximum requis pour les entrées d'une taille donnée. Moins courante, et généralement spécifiée explicitement, est la complexité de cas moyen , qui est la moyenne du temps pris sur les entrées d'une taille donnée (cela est logique car il n'y a qu'un nombre fini d'entrées possibles d'une taille donnée). Dans les deux cas, la complexité temporelle est généralement exprimée en fonction de la taille de l'entrée. Étant donné que cette fonction est généralement difficile à calculer exactement et que le temps d'exécution pour les petites entrées n'est généralement pas conséquent, on se concentre généralement sur le comportement de la complexité lorsque la taille de l'entrée augmente, c'est-à-dire le comportement asymptotique de la complexité. Par conséquent, la complexité temporelle est généralement exprimée en utilisant une grande notation O , généralement , , , , etc., où n est la taille en unités de bits nécessaires pour représenter l'entrée.

Les complexités algorithmiques sont classées selon le type de fonction apparaissant dans la grande notation O. Par exemple, un algorithme à complexité temporelle est un algorithme à temps linéaire et un algorithme à complexité temporelle pour une constante est un algorithme à temps polynomial .

Tableau des complexités temporelles courantes

Le tableau suivant résume certaines classes de complexités temporelles couramment rencontrées. Dans le tableau, poly( x ) = x O (1) , c'est-à-dire polynôme en  x .

Nom Classe de complexité Durée de fonctionnement ( T ( n )) Exemples de temps de parcours Exemples d'algorithmes
temps constant O (1) dix Trouver la valeur médiane dans un tableau trié de nombres

Calculer (−1) n

temps d' Ackermann inverse O ( α ( n )) Temps amorti par opération utilisant un ensemble disjoint
temps logarithmique itéré O ( log *  n ) Coloration distribuée des cycles
log-logarithmique O (log log n ) Temps amorti par opération en utilisant une file d'attente prioritaire limitée
temps logarithmique DLOGTIME O (log  n ) log  n , log( n 2 ) Recherche binaire
temps polylogarithmique poly(log  n ) (log  n ) 2
puissance fractionnaire O ( n c ) 0 < c < 1 n 1/2 , n 2/3 Recherche dans un arbre kd
temps linéaire O ( n ) n , 2 n + 5 Recherche du plus petit ou du plus grand élément dans un tableau non trié , algorithme de Kadane , recherche linéaire
"n étoile de journal n" heure O ( n log * n ) Seidel « s triangulation polygone algorithme.
temps linéaire O ( n log n ) n log n , log n ! Tri de comparaison le plus rapide possible ; Transformée de Fourier rapide .
temps quasi-linéaire n poly(log n )
temps quadratique O ( n 2 ) n 2 Tri à bulles ; Tri par insertion ; Convolution directe
temps cube O ( n 3 ) n 3 Multiplication naïve de deux matrices n × n . Calcul de la corrélation partielle .
Temps polynomial P 2 O (log n ) = poly( n ) n 2 + n , n 10 Algorithme de Karmarkar pour la programmation linéaire ; Test de primalité AKS
temps quasi-polynomial QP 2 poly(log  n ) n journal journal n , n journal  n Algorithme d'approximation O (log 2 n ) le plus connu pour le problème de l'arbre de Steiner dirigé .
temps sous-exponentiel
(première définition)
SUBEXP O (2 n ε ) pour tout ε > 0 Contient BPP sauf si EXPTIME (voir ci-dessous) est égal à MA .
temps sous-exponentiel
(seconde définition)
2 o ( n ) 2 n 1/3 Algorithme le plus connu pour la factorisation d'entiers ; ancien meilleur algorithme pour l' isomorphisme de graphes
temps exponentiel
(avec exposant linéaire)
E 2 O ( n ) 1,1 n , 10 n Résoudre le problème du voyageur de commerce en utilisant la programmation dynamique
temps exponentiel TEMPS EXP 2 poly( n ) 2 n , 2 n 2 Résolution de la multiplication de chaînes matricielles via la recherche par force brute
temps factoriel O ( n !) n ! Résoudre le problème du voyageur de commerce via la recherche par force brute
temps exponentiel double 2-TEMPS D'EXP. 2 2 poly( n ) 2 2 n Décider de la vérité d'un énoncé donné en arithmétique de Presburger

Temps constant

Un algorithme est dit à temps constant (également écrit sous la forme O (1) temps) si la valeur de T ( n ) est bornée par une valeur qui ne dépend pas de la taille de l'entrée. Par exemple, accéder à n'importe quel élément d'un tableau prend un temps constant car une seule opération doit être effectuée pour le localiser. De la même manière, trouver la valeur minimale dans un tableau trié par ordre croissant ; c'est le premier élément. Cependant, trouver la valeur minimale dans un tableau non ordonné n'est pas une opération à temps constant car un balayage sur chaque élément du tableau est nécessaire afin de déterminer la valeur minimale. Il s'agit donc d'une opération de temps linéaire, prenant un temps O ( n ). Si le nombre d'éléments est connu à l'avance et ne change pas, cependant, on peut toujours dire qu'un tel algorithme s'exécute en temps constant.

Malgré le nom "temps constant", le temps d'exécution ne doit pas être indépendant de la taille du problème, mais une limite supérieure pour le temps d'exécution doit être bornée indépendamment de la taille du problème. Par exemple, la tâche « échanger les valeurs d' un et b si si nécessaire que ab » est appelée constante de temps , même si le temps peut dépendre ou non il est déjà vrai que ab . Cependant, il existe une constante t telle que le temps requis est toujours au plus t .

Voici quelques exemples de fragments de code qui s'exécutent en temps constant :

int index = 5;
int item = list[index];
if (condition true) then
    perform some operation that runs in constant time
else
    perform some other operation that runs in constant time
for i = 1 to 100
    for j = 1 to 200
        perform some operation that runs in constant time

Si T ( n ) est O ( n'importe quelle valeur constante ), cela est équivalent et indiqué en notation standard comme T ( n ) étant O (1).

Temps logarithmique

On dit qu'un algorithme prend un temps logarithmique lorsque T ( n ) = O (log n ) . Depuis connecter un  n et log b  n sont liés par un multiplicateur constant , et un tel multiplicateur est hors de propos pour le classement grand-O, l'utilisation standard pour les algorithmes en temps logarithmique est O (log n ) quelle que soit la base du logarithme apparaissant dans l'expression de T .

Les algorithmes prenant un temps logarithmique sont couramment rencontrés dans les opérations sur les arbres binaires ou lors de l'utilisation de la recherche binaire .

Un algorithme O (log n ) est considéré comme très efficace, car le rapport entre le nombre d'opérations et la taille de l'entrée diminue et tend vers zéro lorsque n augmente. Un algorithme qui doit accéder à tous les éléments de son entrée ne peut pas prendre de temps logarithmique, car le temps de lecture d'une entrée de taille n est de l'ordre de n .

Un exemple de temps logarithmique est donné par la recherche dans le dictionnaire. Considérons un dictionnaire D qui contient n entrées, triées par ordre alphabétique . On suppose que, pour 1 ≤ kn , on peut accéder à la k ième entrée du dictionnaire en un temps constant. Soit D ( k ) cette k ème entrée. Sous ces hypothèses, le test pour voir si un mot w est dans le dictionnaire peut être fait en temps logarithmique : considérons , où désigne la fonction plancher . Si , alors nous avons terminé. Sinon, si , continuez la recherche de la même manière dans la moitié gauche du dictionnaire, sinon continuez de la même manière avec la moitié droite du dictionnaire. Cet algorithme est similaire à la méthode souvent utilisée pour trouver une entrée dans un dictionnaire papier.

Temps polylogarithmique

On dit qu'un algorithme s'exécute en temps polylogarithmique si son temps T ( n ) est O ((log n ) k ) pour une constante k . Une autre façon d'écrire ceci est O (log k n ) .

Par exemple, l' ordre des chaînes matricielles peut être résolu en temps polylogarithmique sur une machine parallèle à accès aléatoire , et un graphe peut être déterminé comme planaire de manière entièrement dynamique en un temps O (log 3 n ) par opération d'insertion/suppression.

Temps sous-linéaire

On dit qu'un algorithme s'exécute en temps sous-linéaire (souvent épelé temps sous-linéaire ) si T ( n ) = o ( n ) . Cela inclut en particulier les algorithmes avec les complexités temporelles définies ci-dessus.

Les algorithmes typiques qui sont exacts et pourtant exécutés en temps sous-linéaire utilisent un traitement parallèle (comme le fait le calcul du déterminant de la matrice NC 1 ) ou ont des hypothèses garanties sur la structure d'entrée (comme le font la recherche binaire en temps logarithmique et de nombreux algorithmes de maintenance d'arbre) . Cependant, les langages formels tels que l'ensemble de toutes les chaînes qui ont un bit 1 dans la position indiquée par les premiers bits de log( n ) de la chaîne peuvent dépendre de chaque bit de l'entrée et pourtant être calculables en temps sous-linéaire.

Le terme spécifique algorithme de temps sublinéaire est généralement réservé aux algorithmes qui sont différents de ce qui précède en ce qu'ils sont exécutés sur des modèles de machines en série classiques et ne sont pas autorisés à faire des hypothèses préalables sur l'entrée. Ils sont cependant autorisés à être randomisés , et doivent en effet être randomisés pour toutes les tâches, sauf les plus triviales.

Comme un tel algorithme doit fournir une réponse sans lire l'entièreté de l'entrée, ses particularités dépendent fortement de l'accès autorisé à l'entrée. Habituellement, pour une entrée représentée sous la forme d'une chaîne binaire b 1 ,…, b k, on suppose que l'algorithme peut dans le temps O (1) demander et obtenir la valeur de b i pour tout i .

Les algorithmes temporels sous-linéaires sont généralement aléatoires et ne fournissent que des solutions approximatives . En fait, la propriété d'une chaîne binaire n'ayant que des zéros (et aucun) peut être facilement prouvée comme n'étant pas décidable par un algorithme de temps sous-linéaire (non approximatif). Les algorithmes temporels sous-linéaires apparaissent naturellement dans l'investigation des tests de propriétés .

Temps linéaire

On dit qu'un algorithme prend un temps linéaire , ou O ( n ) temps, si sa complexité temporelle est O ( n ) . De manière informelle, cela signifie que le temps d'exécution augmente au plus linéairement avec la taille de l'entrée. Plus précisément, cela signifie qu'il existe une constante c telle que le temps d'exécution est d'au plus cn pour chaque entrée de taille n . Par exemple, une procédure qui additionne tous les éléments d'une liste nécessite un temps proportionnel à la longueur de la liste, si le temps d'addition est constant, ou, au moins, délimité par une constante.

Le temps linéaire est la meilleure complexité temporelle possible dans les situations où l'algorithme doit lire séquentiellement l'intégralité de son entrée. Par conséquent, de nombreuses recherches ont été investies dans la découverte d'algorithmes présentant un temps linéaire ou, au moins, un temps presque linéaire. Cette recherche comprend à la fois des méthodes logicielles et matérielles. Il existe plusieurs technologies matérielles qui exploitent le parallélisme pour fournir cela. Un exemple est la mémoire adressable par le contenu . Ce concept de temps linéaire est utilisé dans les algorithmes de correspondance de chaînes tels que l'algorithme de Boyer-Moore et l' algorithme d' Ukkonen .

Temps quasi-linéaire

On dit qu'un algorithme s'exécute en temps quasi-linéaire (également appelé temps log-linéaire ) si T ( n ) = O ( n log k n ) pour une constante positive k ; le temps linéaire est le cas k = 1 . En utilisant la notation soft O, ces algorithmes sont Õ( n ). Les algorithmes temporels quasi-linéaires sont également O ( n 1+ ε ) pour chaque constante ε > 0, et s'exécutent donc plus rapidement que tout algorithme temporel polynomial dont la limite temporelle inclut un terme n c pour tout c > 1 .

Les algorithmes qui s'exécutent en temps quasi-linéaire comprennent :

Dans de nombreux cas, le temps d'exécution n log n est simplement le résultat de l'exécution d'une opération Θ(log n ) n fois (pour la notation, voir Big O notation § Family of Bachmann-Landau notations ). Par exemple, le tri par arbre binaire crée un arbre binaire en insérant un par un chaque élément du tableau de taille n . Étant donné que l'opération d'insertion sur un arbre de recherche binaire auto-équilibré prend un temps O (log n ), l'ensemble de l'algorithme prend un temps O ( n log n ) .

Les tris par comparaison nécessitent au moins Ω( n log n ) comparaisons dans le pire des cas car log( n !) = Θ( n log n ) , selon l'approximation de Stirling . Ils résultent aussi fréquemment de la relation de récurrence T ( n ) = 2 T ( n /2) + O ( n ) .

Temps sous-quadratique

Un algorithme est dit en temps subquadratique si T ( n ) = o ( n 2 ) .

Par exemple, des algorithmes de tri simples basés sur la comparaison sont quadratiques (par exemple, par insertion sort ), mais des algorithmes plus avancés peuvent être trouvés sous- quadratiques (par exemple, shell sort ). Aucun tri général n'est exécuté en temps linéaire, mais le passage du quadratique au sous-quadratique est d'une grande importance pratique.

Temps polynomial

Un algorithme est dit à temps polynomial si son temps d'exécution est majoré par une expression polynomiale de la taille de l'entrée de l'algorithme, c'est-à-dire T ( n ) = O ( n k ) pour une constante positive k . Les problèmes pour lesquels un algorithme en temps polynomial déterministe existe appartiennent à la classe de complexité P , qui est centrale dans le domaine de la théorie de la complexité computationnelle . La thèse de Cobham affirme que le temps polynomial est synonyme de « traitable », « faisable », « efficace » ou « rapide ».

Quelques exemples d'algorithmes en temps polynomial :

  • L' algorithme de tri par sélection sur n entiers effectue des opérations pour une constante A . Ainsi, il s'exécute dans le temps et est un algorithme en temps polynomial.
  • Toutes les opérations arithmétiques de base (addition, soustraction, multiplication, division et comparaison) peuvent être effectuées en temps polynomial.
  • Les correspondances maximales dans les graphiques peuvent être trouvées en temps polynomial.

Temps fortement et faiblement polynomial

Dans certains contextes, notamment en optimisation , on distingue les algorithmes en temps fortement polynomial et en temps faiblement polynomial . Ces deux concepts ne sont pertinents que si les entrées des algorithmes sont constituées d'entiers.

Le temps fortement polynomial est défini dans le modèle arithmétique de calcul. Dans ce modèle de calcul, les opérations arithmétiques de base (addition, soustraction, multiplication, division et comparaison) nécessitent un pas de temps unitaire à effectuer, quelle que soit la taille des opérandes. L'algorithme s'exécute en temps fortement polynomial si :

  1. le nombre d'opérations dans le modèle arithmétique de calcul est borné par un polynôme du nombre d'entiers dans l'instance d'entrée ; et
  2. l'espace utilisé par l'algorithme est délimité par un polynôme de la taille de l'entrée.

Tout algorithme avec ces deux propriétés peut être converti en un algorithme de temps polynomial en remplaçant les opérations arithmétiques par des algorithmes appropriés pour effectuer les opérations arithmétiques sur une machine de Turing . Si la deuxième des conditions ci-dessus n'est pas remplie, alors ce n'est plus vrai. Étant donné l'entier (qui occupe un espace proportionnel à n dans le modèle de la machine de Turing), il est possible de calculer avec n multiplications en utilisant la quadrature répétée . Cependant, l'espace utilisé pour représenter est proportionnel à , et donc exponentiel plutôt que polynomial dans l'espace utilisé pour représenter l'entrée. Par conséquent, il n'est pas possible d'effectuer ce calcul en temps polynomial sur une machine de Turing, mais il est possible de le calculer polynomialement par de nombreuses opérations arithmétiques.

Inversement, il existe des algorithmes qui s'exécutent dans un certain nombre d'étapes de la machine de Turing délimitées par un polynôme dans la longueur de l'entrée codée en binaire, mais ne prennent pas un certain nombre d'opérations arithmétiques limitées par un polynôme dans le nombre de nombres d'entrée. L' algorithme euclidien pour calculer le plus grand diviseur commun de deux entiers en est un exemple. Étant donné deux nombres entiers et , l'algorithme effectue des opérations arithmétiques sur des nombres avec au plus des bits. En même temps, le nombre d'opérations arithmétiques ne peut pas être borné par le nombre d'entiers en entrée (qui est constant dans ce cas, il n'y a toujours que deux entiers en entrée). En raison de cette dernière observation, l'algorithme ne s'exécute pas en temps fortement polynomial. Son temps d'exécution réel dépend des grandeurs et et pas seulement du nombre d'entiers dans l'entrée.

Un algorithme qui s'exécute en temps polynomial mais qui n'est pas fortement polynomial est dit s'exécuter en temps faiblement polynomial . Un exemple bien connu d'un problème pour lequel un algorithme en temps faiblement polynomial est connu, mais n'est pas connu pour admettre un algorithme en temps fortement polynomial, est la programmation linéaire . Le temps faiblement polynomial ne doit pas être confondu avec le temps pseudo-polynomial .

Classes de complexité

Le concept de temps polynomial conduit à plusieurs classes de complexité dans la théorie de la complexité computationnelle. Certaines classes importantes définies à l'aide du temps polynomial sont les suivantes.

P La classe de complexité des problèmes de décision qui peuvent être résolus sur une machine de Turing déterministe en temps polynomial
NP La classe de complexité des problèmes de décision qui peuvent être résolus sur une machine de Turing non déterministe en temps polynomial
ZPP La classe de complexité des problèmes de décision qui peuvent être résolus sans erreur sur une machine de Turing probabiliste en temps polynomial
PR La classe de complexité des problèmes de décision qui peuvent être résolus avec une erreur unilatérale sur une machine de Turing probabiliste en temps polynomial.
BPP La classe de complexité des problèmes de décision qui peuvent être résolus avec une erreur bilatérale sur une machine de Turing probabiliste en temps polynomial
BQP La classe de complexité des problèmes de décision qui peuvent être résolus avec une erreur bilatérale sur une machine de Turing quantique en temps polynomial

P est la plus petite classe de complexité temporelle sur une machine déterministe qui est robuste en termes de changements de modèle de machine. (Par exemple, le passage d'une machine de Turing à une seule bande à une machine à plusieurs bandes peut entraîner une accélération quadratique, mais tout algorithme qui s'exécute en temps polynomial sous un modèle le fait également sur l'autre.) Toute machine abstraite donnée le fera. ont une classe de complexité correspondant aux problèmes qui peuvent être résolus en temps polynomial sur cette machine.

Temps superpolynomial

On dit qu'un algorithme prend un temps superpolynomial si T ( n ) n'est limité au-dessus par aucun polynôme. En utilisant peu de notation oméga , il s'agit du temps ω ( n c ) pour toutes les constantes c , où n est le paramètre d'entrée, généralement le nombre de bits dans l'entrée.

Par exemple, un algorithme qui s'exécute sur 2 n étapes sur une entrée de taille n nécessite un temps superpolynomial (plus précisément, un temps exponentiel).

Un algorithme qui utilise des ressources exponentielles est clairement superpolynomial, mais certains algorithmes ne sont que très faiblement superpolynomiaux. Par exemple, le test de primalité Adleman-Pomerance-Rumely s'exécute pendant n O (log log n ) sur des entrées n bits ; celui-ci croît plus rapidement que n'importe quel polynôme pour un n suffisamment grand , mais la taille d'entrée doit devenir trop grande avant qu'elle ne puisse être dominée par un polynôme de petit degré.

Un algorithme qui nécessite un temps superpolynomial se situe en dehors de la classe de complexité P . La thèse de Cobham postule que ces algorithmes ne sont pas pratiques, et dans de nombreux cas, ils le sont. Puisque le problème P contre NP n'est pas résolu, on ne sait pas si les problèmes NP-complets nécessitent un temps superpolynomial.

Temps quasi-polynomial

Les algorithmes de temps quasi polynomial sont des algorithmes qui s'exécutent plus longtemps que le temps polynomial, mais pas assez longtemps pour être un temps exponentiel. Le pire des cas de temps d'exécution d'un algorithme de temps quasi-polynomial est pour certains fixes . Car nous obtenons un algorithme de temps polynomial, car nous obtenons un algorithme de temps sous-linéaire.

Les algorithmes temporels quasi-polynomiaux surviennent généralement lors de réductions d'un problème NP-difficile à un autre problème. Par exemple, on peut prendre une instance d'un problème difficile NP, disons 3SAT , et la convertir en une instance d'un autre problème B, mais la taille de l'instance devient . Dans ce cas, cette réduction ne prouve pas que le problème B est NP-difficile ; cette réduction montre seulement qu'il n'y a pas d'algorithme de temps polynomial pour B à moins qu'il n'y ait un algorithme de temps quasi-polynomial pour 3SAT (et donc tout NP ). De même, il existe certains problèmes pour lesquels on connaît des algorithmes en temps quasi polynomial, mais aucun algorithme en temps polynomial n'est connu. De tels problèmes se posent dans les algorithmes d'approximation ; un exemple célèbre est le problème d'arbre de Steiner dirigé , pour lequel il existe un algorithme d'approximation en temps quasi polynomial atteignant un facteur d'approximation de ( n étant le nombre de sommets), mais montrer l'existence d'un tel algorithme en temps polynomial est un problème ouvert.

D'autres problèmes de calcul avec des solutions de temps quasi-polynomiales mais aucune solution de temps polynomiale connue incluent le problème de clique plantée dans lequel le but est de trouver une grande clique dans l'union d'une clique et d'un graphe aléatoire . Bien que quasi-polynomialement résoluble, il a été conjecturé que le problème de la clique plantée n'a pas de solution en temps polynomial ; cette conjecture de clique plantée a été utilisée comme hypothèse de dureté de calcul pour prouver la difficulté de plusieurs autres problèmes dans la théorie des jeux informatiques , les tests de propriétés et l' apprentissage automatique .

La classe de complexité QP comprend tous les problèmes qui ont des algorithmes de temps quasi-polynomiaux. Il peut être défini en termes de DTIME comme suit.

Relation avec les problèmes NP-complets

En théorie de la complexité, le problème non résolu P contre NP demande si tous les problèmes de NP ont des algorithmes en temps polynomial. Tous les algorithmes les plus connus pour les problèmes NP-complets comme 3SAT etc. prennent un temps exponentiel. En effet, il est conjecturé pour de nombreux problèmes naturels NP-complets qu'ils n'ont pas d'algorithmes de temps sous-exponentiels. Ici, « temps sous-exponentiel » est pris pour signifier la deuxième définition présentée ci-dessous. (D'autre part, de nombreux problèmes de graphes représentés de manière naturelle par des matrices d'adjacence sont résolvables en temps sous-exponentiel simplement parce que la taille de l'entrée est le carré du nombre de sommets.) Cette conjecture (pour le problème k-SAT) est connue sous le nom d' hypothèse du temps exponentiel . Puisqu'il est conjecturé que les problèmes NP-complets n'ont pas d'algorithmes de temps quasi-polynomiaux, certains résultats d'inapproximation dans le domaine des algorithmes d'approximation font l'hypothèse que les problèmes NP-complets n'ont pas d'algorithmes de temps quasi-polynomiaux. Par exemple, consultez les résultats d'inapproximation connus pour le problème de couverture d'ensemble .

Temps sous-exponentiel

Le terme sous-exponentielle du temps est utilisé pour exprimer que le temps d' exécution d' un certain algorithme peut croître plus vite que tout polynôme mais reste nettement inférieur à une exponentielle. En ce sens, les problèmes qui ont des algorithmes de temps sous-exponentiels sont un peu plus traitables que ceux qui n'ont que des algorithmes exponentiels. La définition précise de "sous-exponentiel" n'est généralement pas acceptée, et nous énumérons ci-dessous les deux plus largement utilisées.

Première définition

Un problème est dit résoluble en temps sous-exponentiel s'il peut être résolu en temps d'exécution dont les logarithmes deviennent plus petits que n'importe quel polynôme donné. Plus précisément, un problème est dans le temps de sous-exponentielle si pour tout ε > 0 , il existe un algorithme qui permet de résoudre le problème dans le temps O (2 n ε ). L'ensemble de tous ces problèmes est la classe de complexité SUBEXP qui peut être définie en termes de DTIME comme suit.

Cette notion de sous-exponentielle n'est pas uniforme en termes de ε dans le sens où ε ne fait pas partie de l'entrée et chaque ε peut avoir son propre algorithme pour le problème.

Deuxième définition

Certains auteurs définissent le temps sous-exponentiel comme des temps d'exécution en 2 o ( n ) . Cette définition permet des temps d'exécution plus longs que la première définition du temps sous-exponentiel. Un exemple d'un tel algorithme de temps sous-exponentiel est l'algorithme classique le plus connu pour la factorisation d'entiers, le tamis de champ de nombre général , qui s'exécute dans le temps environ , où la longueur de l'entrée est n . Un autre exemple était le problème d'isomorphisme de graphe , que l'algorithme le plus connu de 1982 à 2016 a résolu dans . Cependant, au STOC 2016, un algorithme de temps quasi-polynomial a été présenté.

Cela fait une différence si l'algorithme est autorisé à être sous-exponentiel dans la taille de l'instance, le nombre de sommets ou le nombre d'arêtes. Dans la complexité paramétrée , cette différence est rendue explicite en considérant des paires de problèmes de décision et de paramètres k . SUBEPT est la classe de tous les problèmes paramétrés qui s'exécutent en temps sous-exponentiel en k et polynomial en entrée de taille n :

Plus précisément, SUBEPT est la classe de tous les problèmes paramétrés pour lesquels il existe une fonction calculable avec et un algorithme qui décide L en temps .

Hypothèse de temps exponentiel

L' hypothèse du temps exponentiel ( ETH ) est que 3SAT , le problème de satisfiabilité des formules booléennes sous forme normale conjonctive avec au plus trois littéraux par clause et avec n variables, ne peut pas être résolu en temps 2 o ( n ) . Plus précisément, l'hypothèse est qu'il existe une constante absolue c > 0 telle que 3SAT ne puisse être décidée en temps 2 cn par aucune machine de Turing déterministe. Avec m désignant le nombre de clauses, ETH est équivalent à l'hypothèse que k SAT ne peut pas être résolu en temps 2 o ( m ) pour tout entier k 3 . L'hypothèse du temps exponentiel implique P NP .

Temps exponentiel

Un algorithme est dit à temps exponentiel , si T ( n ) est majoré par 2 poly( n ) , où poly( n ) est un polynôme dans n . Plus formellement, un algorithme est un temps exponentiel si T ( n ) est borné par O (2 n k ) pour une constante k . Les problèmes qui admettent des algorithmes à temps exponentiel sur une machine de Turing déterministe forment la classe de complexité connue sous le nom d' EXP .

Parfois, le temps exponentiel est utilisé pour désigner des algorithmes qui ont T ( n ) = 2 O ( n ) , où l'exposant est au plus une fonction linéaire de n . Cela donne lieu à la classe de complexité E .

Temps factoriel

Un exemple d'algorithme qui s'exécute en temps factoriel est bogosort , un algorithme de tri notoirement inefficace basé sur des essais et des erreurs . Bogosort trie une liste de n éléments en mélangeant à plusieurs reprises la liste jusqu'à ce qu'elle soit triée. Dans le cas moyen, chaque passage dans l'algorithme bogosort examinera l'un des n ! commandes des n articles. Si les articles sont distincts, un seul de ces ordres est trié. Bogosort partage le patrimoine avec le théorème du singe infini .

Temps exponentiel double

Un algorithme est dit à temps exponentiel double si T ( n ) est majoré par 2 2 poly( n ) , où poly( n ) est un polynôme dans n . De tels algorithmes appartiennent à la classe de complexité 2-EXPTIME .

Les algorithmes de temps exponentiel double bien connus incluent :

Voir également

Les références