On generic complexity of solving of equations in finite predicate algebraic structures | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 70. DOI: 10.17223/20710410/70/6

In this paper, we study the generic complexity of two variants of the problem of solving equations without constants over finite predicate algebraic systems: the solvability recognition problem and the solution search problem. For both problems, efficient polynomial algorithms are not known in many cases. We propose a polynomial generic algorithm for the solvability recognition problem. On the other hand, for the solution search problem, we prove that if there is no polynomial probabilistic algorithm for it, then there is a subproblem of this problem for which there is no polynomial generic algorithm. The obtained result is a theoretical justification for possible applications of the solution search problem in cryptography, where the problem of breaking a cryptographic algorithm is required to 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 main ingredient of this method is a technique of cloning, which unites inputs of the problem together in the large enough sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.