Abstract: We study the generic complexity of the problem of solving systems of equations in the Skolem form over finitely generated monoids. Three variants of this problem are considered. The first variant is the problem of recognizing the solvability of dense systems of equations, where the number of equations is bounded cubically in the number of variables. For this problem, we prove its strongly generic decidability in polynomial time. The second variant is a similar problem for sparse systems of equations, where the number of equations is bounded linearly in the number of variables. For this problem, we prove that, given its worstcase intractability, no strongly generic polynomial algorithm exists. This means that for any generic polynomial algorithm, there exists an efficient method for randomly generating inputs on which this algorithm cannot solve the problem. Finally, the third variant is the problem of searching solutions to systems of equations. For this problem, the input is a system of equations for which a solution is known to exist and at least one solution must be found. Search problems find application in cryptography, where a solution is always known to exist and this solution must be found. For the search problem, it is proven that, given its intractability, there exists a subproblem of this problem for which there is no generic polynomial algorithm.

Cite: Рыбалов А.Н. , Шевляков А.Н.
О генерической сложности проблемы решения уравнений в форме Сколема над моноидами
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2026. Т.23. №1. С.244-256. DOI: 10.33048/semi.2026.23.015

Dates:

Submitted:	Jan 12, 2026
Accepted:	Feb 2, 2026
Published print:	Mar 25, 2026
Published online:	Mar 25, 2026

Identifiers: No identifiers

Altmetrics: