On the generic complexity of solving equations over~natural numbers with addition

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 72-78

Résumé

We study the general complexity of the problem of determining the solvability of equations systems over natural numbers with the addition. The $\text{NP}$-completeness of this problem is proved. A polynomial generic algorithm for solving this problem is proposed. It is proved that if $\text{P} \neq \text{NP}$ and $\text{P} = \text{BPP}$, then for the problem of checking the solvability of systems of equations over natural numbers with zero there is no strongly generic polynomial algorithm. For a strongly generic polynomial algorithm, there is no efficient method for random generation of inputs on which the algorithm cannot solve the problem. To prove this theorem, we use the method of generic amplification, which allows us to construct generically hard problems from problems that are hard in the classical sense. The main feature of this method is the cloning technique, 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.

Détail

Keywords: generic complexity, linear equations, natural numbers.