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
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