Geodesic
On generic complexity of equation solving over~the~bicyclic monoid
Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 110-117.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we study computational complexity of the problem of determining solvability equations over bicyclic monoid. This monoid, in addition to its theoretical significance in topology and semigroup theory, has applications in computer science and programming languages, for example, as a model for the Dyck language of balanced bracket expressions. We prove $\text{NP}$-completeness of the problem of determining solvability equations over bicyclic monoid. Also, we prove that if $\text{P} \neq \text{NP}$ and $\text{P} = \text{BPP}$, then for this problem there is no strongly generic polynomial algorithm. This means that for any generic polynomial algorithm there exists an efficient method of randomly generating inputs on which the algorithm cannot solve the problem under consideration. The result points to a possible application of this problem in cryptography, where it is necessary that the problem of breaking a cryptosystem be hard for almost all inputs. To prove this theorem, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense. The basis of this method is a technique of cloning, which combines the input data of a problem into sufficiently large sets of equivalent input data. Equivalence is understood in the sense that the problem is solved similarly for them.
Keywords: generic complexity, $\text{NP}$-completeness, bicyclic monoid. 
@article{PDM_2025_1_a6,
     author = {A. A. Lopatin and A. N. Rybalov},
     title = {On generic complexity of equation solving over~the~bicyclic monoid},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {110--117},
     publisher = {mathdoc},
     number = {1},
     year = {2025},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2025_1_a6/}
}
TY  - JOUR
AU  - A. A. Lopatin
AU  - A. N. Rybalov
TI  - On generic complexity of equation solving over~the~bicyclic monoid
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2025
SP  - 110
EP  - 117
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2025_1_a6/
LA  - ru
ID  - PDM_2025_1_a6
ER  - 
%0 Journal Article
%A A. A. Lopatin
%A A. N. Rybalov
%T On generic complexity of equation solving over~the~bicyclic monoid
%J Prikladnaâ diskretnaâ matematika
%D 2025
%P 110-117
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2025_1_a6/
%G ru
%F PDM_2025_1_a6
A. A. Lopatin; A. N. Rybalov. On generic complexity of equation solving over~the~bicyclic monoid. Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 110-117. http://geodesic.mathdoc.fr/item/PDM_2025_1_a6/

[1] Baumslag G., Myasnikov A., and Remeslennikov V., “Algebraic geometry over groups I. Algebraic sets and ideal theory”, J. Algebra, 219:1 (1999), 16–79 | DOI | MR

[2] Shevlyakov A. N., “Equationally Noetherian varieties of semigroups and B. Plotkin's problem”, Siberian Electronic Math. Reports, 20:2 (2023), 724–734 | MR

[3] Shevlyakov A. N., “Wreath products of semigroups and Plotkin's problem”, Algebra i Logika, 62:5 (2023), 665–691 (in Russian)

[4] Rybalov A. N., “On complexity of solving of equations over graphs”, Siberian Electronic Math. Reports, 21:1 (2024), 62–69 (in Russian) | MR

[5] Nikitin A. Yu. and Shevlyakov A. N., “On radicals over strict partial order sets”, J. Physics: Conf. Ser., 1791 (2021), 012080, 6 pp. | DOI

[6] Kapovich I., Miasnikov A., Schupp P., and Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR

[7] Rybalov A. and Shevlyakov A., “Generic complexity of solving of equations in finite groups, semigroups and fields”, J. Physics: Conf. Ser., 1901 (2021), 012047, 8 pp. | DOI

[8] Hopcroft J. E. and Ullman J. D., Formal Languages and Their Relation to Automata, Addison-Wesley, 1969, 288 pp. | MR

[9] Diekert V. and Lohrey M., “Word equations over graph products”, Intern. J. Algebra Computation, 18:3 (2008), 493–533 | DOI | MR

[10] Kitaev A., Shen' A., and Vyalyy M., Classical and Quantum Computations, MCCME Publ., M., 1999, 192 pp. (in Russian)

[11] Schrijver A., “Theory of Linear and Integer Programming”, Wiley, 1998, 484 pp. | MR | MR