Geodesic
On complexity of the word problem in semigroups with homogeneous relations
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 55-61 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: computational complexity, semigroups, word problem. 
@article{SEMR_2024_21_1_a1,
     author = {A. N. Rybalov},
     title = {On complexity of the word problem in semigroups with homogeneous relations},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {55--61},
     year = {2024},
     volume = {21},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On complexity of the word problem in semigroups with homogeneous relations
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 55
EP  - 61
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/
LA  - ru
ID  - SEMR_2024_21_1_a1
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On complexity of the word problem in semigroups with homogeneous relations
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 55-61
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/
%G ru
%F SEMR_2024_21_1_a1
A. N. Rybalov. On complexity of the word problem in semigroups with homogeneous relations. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 55-61. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/

[1] S.I. Adjan, V.G. Durnev, “Decision problems for groups and semigroups”, Russ. Math. Surv., 55:2 (2000), 207–296 | DOI | MR | Zbl

[2] E.W. Cardoza, Computational complexity of the word problem for commutative semigroups, MAC technical memorandum, 67, MIT, 1975 https://dspace.mit.edu/handle/1721.1/148895

[3] V. Diekert, Y. Métivier, “Partial commutation and traces”, Handbook of Formal Languages, eds. in Rozenberg, G., Salomaa, A., Springer-Verlag, Berlin–Heidelberg, 1997, 457–534 | DOI | MR

[4] M. Garey, D. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman and Company, San Francisco, 1979 https://bohr.wlu.ca/hfan/cp412/references/ChapterOne.pdf | Zbl

[5] E. Mayr, A. Meyer, “The complexity of the word problems for commutative semigroups and polynomial ideals”, Adv. Math., 46 (1982), 305–329 https://core.ac.uk/download/pdf/82035833.pdf | DOI | Zbl

[6] A.I. Malcev, “On homomorphisms of finite groups”, Uch. Zapiski Ivanovskogo Ped. Instituta, 18 (1958), 49–60

[7] A.A. Markov, “Impossibility of some algorithms in the theory of associative systems”, Doklady AN SSSR, 55:7 (1947), 587–590 | MR

[8] P.S. Novikov, “On algorithmic undecidability of the word problem in group theory”, Tr. Mat. Inst. Steklova, 44, 1955 | MR | Zbl

[9] E.L. Post, “Recursive unsolvability of a problem of Thue”, J. Symb. Log., 12 (1947), 1–11 https://www.wolframscience.com/prizes/tm23/images/Post2.pdf | DOI | Zbl

[10] W.J. Savitch, “Relationships between nondeterministic and deterministic tape complexities”, J. Comput. Syst. Sci., 4:2 (1970), 177–192 https://www.sciencedirect.com/science/article/pii/S002200007080006X | DOI | MR | Zbl