ON GENERIC COMPLEXITY OF EQUATION SOLVING OVER THE BICYCLIC MONOID

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 NP-completeness of the problem of determining solvability equations over bicyclic monoid. Also, we prove that if P 6= NP and P = 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.