Abstract: In this paper we study the computational complexity of the word problem in semigroups with the condition of homogeneity of the de fining relations. These are finitely de fined semigroups, in which for each de fining 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 de fining 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 de fining relations with the intractable problem of equality.

Cite: Рыбалов А.Н.
О сложности проблемы равенства в полугруппах с условием однородности определяющих соотношений
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. Т.21. №1. С.55-61. DOI: 10.33048/semi.2024.21.004 WOS Scopus РИНЦ

Dates:

Submitted:	Nov 23, 2023
Accepted:	Jan 2, 2024
Published print:	Feb 13, 2024
Published online:	Feb 13, 2024

Identifiers:

Web of science:	WOS:001164416300004
Scopus:	2-s2.0-85195453598
Elibrary:	82336230

Citing: Пока нет цитирований

Altmetrics: