J.-C. Birget Time complexity of the word problem for semigroups and the Higman embedding theorem La complexité temporelle du problème du mot pour les semi­ groupes finiment engendrés reçoit la caractérisation algébrique suivante, sous forme d'un raffinement du théorème d'inclusion de Higman : Soit S un semigroupe finiment engendré dont le problème du mot a une complexité temporelle non-déterministe T (où T est une fonction sur les entiers positifs qui est suradditive, càd que T(n+m) . T(n) + T(m)). Alors S peut être inclus dans un semi­ groupe finiment présenté H dans lequel la distance de dérivation entre deux mots équivalents quelconques x et y (donc la fonc­ tion isopérimétrique) est inférieure ou égale à T(|x| + |y|) 2. De plus, il existe une réduction conjonctive en temps linéaire du problème du mot de H au problème du mot de S. Donc les problèmes du mot de H et de S ont la même complexité temporelle non-déterministe (et aussi la même complexité temporelle déterministe). Un semigroupe finiment engendré S a un problème du mot dans NTIME(T) (ou dans DTIME(T0)) ssi S peut être inclus dans un semigroupe finiment présenté H dont le problème du mot appartient à NTIME(T) (resp. DTIME(T0)). Inversement, si un semigroupe finiment engendré S est inclus dans un semigroupe finiment présenté H dont la fonction isopérimétrique est . D (où D(n) . n), alors le problème du mot de S a une complexité temporelle non déterministe . D. Le problème du mot d'un semigroupe finiment engendré S appar­ tient à NP (ou plus généralement à NTIME(TO(1) )) ssi S peut être inclus dans un semigroupe finiment présenté H ayant une fonction isopérimétrique polynomiale (resp. dans TO(1).). Un problème algorithmique L est dans NP (ou plus généralement dans NTIME(TO(1) )) ssi L peut être réduit (par réduction linéaire injective) au problème du mot d'un semigroupe finiment engendré ayant une fonction isopérimétrique polynomiale (resp. dans TO(1).). Essentiellement, ceci montre que : (1) trouver des inclusions dans des semigroupes ou des groupes finiment présentés est un analogue algébrique de la notion d'algorithmes non déterministes; (2) la fonction isopérimétrique est un analogue algébrique de la complexité temporelle non déterministe. The following algebraic characterization of the complexity of the word problem for finitely generated semigroups is proved, in the form of a refinement of the Higman Embedding Theorem.: Let S be a finitely generated semigroup whose word problem has non deterministic time complexity T (where T is a function on the positive integers which is superadditive, that is, T(n+m) . T(n) + T(m)). Then S can be embedded in a finitely presented semigroup H in which the derivation distance between any two equivalent words x and y (and hence the isoperimetric function) is . T(|x| + |y|) 2. Moreover, there is a conjunctive linear-time reduction from the word problem of H to the word problem of S, so the word problems of H and S have the same non-deterministic time complexity (and also the same deterministic time complexity). A finitely generat­ ed semigroup S has a word problem in NTIME(T) (or in DTIME(T0)) iff S is embeddable into a finitely presented semigroup H whose word problem is in NTIME(T) (resp. DTIME(T0)). Conversely, if a finitely generated semigroup S is embeddable in a finitely presented semigroup H whose isoperimetric function is . D (where D(n) . n), then the word problem of S has non- deterministic time complexity . D. The word problem of a finitely generated semigroup S is in NP (or more generally in NTIME(TO(1) )) iff S can be embedded in a finitely presented semigroup H with polynomial (resp. TO(1).) isoperimetric function. An algorithmic problem L is in NP (or more generally in NTIME(TO(1) )) iff L is reducible (via a linear-time one-to-one reduction) to the word problem of a finitely presented semigroup with polynomial (resp. TO(1).) isoperimetric function. In essence, this shows that: (1) finding embeddings into finitely presented semigroups or groups is an algebraic analogue of non-deterministic algorithm design; (2).the isoperimetric function is an algebraic analogue of the non-deterministic time complexity.