Аннотация:
In this paper we study the computational complexity of the word problem in semigroups with the condition of homogeneity of the defining relations. These are finitely defined semigroups, in which for each defining relation the lengths of the left and right parts are equal. The word problem for such semigroups is decidable, but known algorithms require exponential time and memory. We prove that this problem belongs to the class PSPACE, consisting of algorithmic problems that are solved by Turing machines using space (memory cells) bounded polynomially. This improves the upper bound on the space complexity known before. On the other hand, we prove that there exists a semigroup with the condition of homogeneity of defining relations, in which the equality problem is complete in the class PSPACE with respect to polynomial reducibility. It is assumed (although not proven) that the class PSPACE is wider than the class NP and, even more so, the class P. Thus, it is shown that there are semigroups with the condition of homogeneity of defining relations with the intractable problem of equality.
Ключевые слова:computational complexity, semigroups, word problem.