RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2024, том 21, выпуск 1, страницы 55–61 (Mi semr1667)

Математическая логика, алгебра и теория чисел

О сложности проблемы равенства в полугруппах с условием однородности определяющих соотношений

А. Н. Рыбалов

Sobolev Institute of Mathematics, prospekt Koptyuga 4, Novosibirsk, 630090, Russia

Аннотация: 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.

УДК: 510.652

MSC: 11U99

Поступила 23 ноября 2023 г., опубликована 13 февраля 2024 г.

DOI: doi.org/10.33048/semi.2024.21.004



© МИАН, 2024