Time complexity of the word problem for semigroups and the Higman embedding theorem

J.-C. Birget

IBP-Litp 1995/26: Rapport de Recherche Litp / Litp research reports
69 pages - Juin/June 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Time complexity of the word problem for semigroups and the Higman embedding theorem

Résumé : La complexité temporelle du problème du mot pour les semigroupes 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 semigroupe finiment présenté H dans lequel la distance de dérivation entre deux mots équivalents quelconques x et y (donc la fonction 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 appartient à 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.

Abstract : 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 generated 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.

Publications internes Litp 1995 / Litp research reports 1995