On the generic complexity of solving equations over natural numbers with addition | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/6

We study the general complexity of the problem of determining the solvability of equations systems over natural numbers with the addition. The NP-completeness of this problem is proved. A polynomial generic algorithm for solving this problem is proposed. It is proved that if P ≠ NP and P = 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.
Download file
Counter downloads: 8
  • Title On the generic complexity of solving equations over natural numbers with addition
  • Headline On the generic complexity of solving equations over natural numbers with addition
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 64
  • Date:
  • DOI 10.17223/20710410/64/6
Keywords
generic complexity, linear equations, natural numbers
Authors
References
Kapovich L, Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P.665-694.
Gilman R. H., Myasnikov A., and Roman'kov V. Random equations in free groups // Groups Complexity Cryptology. 2011. V.3. No. 2. P.257-284.
Gilman R. H., Myasnikov A., and Roman'kov V. Random equations in nilpotent groups //j. Algebra. 2012. V.352. No. 1. P. 192-214.
Rybalov A. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V.5. No. 1. P.25-30.
Rybalov A. and Shevlyakov A. Generic complexity of solving of equations in finite groups, semigroups and fields //j. Physics: Conf. Ser. 2021. V. 1901. Article 012047. 8p.
Shevlyakov A. Algebraic geometry over the additive monoid of natural numbers: The classifcation of coordinate monoids // Groups Complexity Cryptology. 2010. V. 2. No. 1. P.91-111.
Шевляков A. H. Алгебраическая геометрия над моноидом натуральных чисел. Неприводимые алгебраические множества // Труды Института математики и механики УрО РАН. 2010. Т. 16. №2. С. 258-269.
Kryvyi S. L.Compatibility of systems of linear constraints over the set of natural numbers // Cybernetics Systems Analysis. 2002. V. 38. No. 1. P. 17-29.
Китаев А., Шенъ А., Вялый M. Классические и квантовые вычисления. М.: Ml LI INK). ЧеРо, 1999. 192 c.
Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991. 360 с.
 On the generic complexity of solving equations over natural numbers with addition | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/6
On the generic complexity of solving equations over natural numbers with addition | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/6
Download full-text version
Counter downloads: 141