Abstract
The following algebraic characterization of the computational 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 nondeterministic time complexity T (where T is a function on the positive integers which is superadditive, i.e. 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
O(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 S and H have the same nondeterministic
time complexity (and also the same deterministic time complexity). Thus, a finitely generated semigroup S has a word problem in NTIME(T) (or in DTIME(To)) iff S is embeddable into a finitely presented semigroup H whose word problem is in NTIME(T) (respectively in DTIME(To)).
In the other direction, if a finitely generated semigroup S is embeddable in a finitely presented semigroup H with
isoperimetric function ≤ D (where D(n) ≥ n), then the word problem of S has nondeterministic time complexity
O(D).
The word problem of a finitely generated semigroup S is in NP (or more generally, in NTIME((T)O(1))) iff S can be embedded in a finitely presented semigroup
H with polynomial (respectively (T)O(1)) isoperimetric function.
An algorithmic problem L is in NP (or more generally, in NTIME((T)O(1))) iff L is reducible (via a linear-time one-to-one reduction) to the word problem of a finitely presented semigroup with polynomial (respectively (T)O(1)) isoperimetric function.
In essence, this shows: (1) Finding embeddings into finitely presented semigroups or groups is an algebraic analogue of
nondeterministic algorithm design; (2) the isoperimetric function is an algebraic analogue of nondeterministic time complexity.