A solution is called binary if each variable is equal to either zero or one. It is well known that it is hard to find a binary solution to the system of algebraic equations in which the coefficients are integers with small absolute values. The aim of the paper is to propose an effective probabilistic reduction of the system to a new equation when there is a small difference between the number of binary solutions to the first equation and the number of binary solutions to the entire system. The proposed method is based on replacing the given system of equations with a linear combination of these equations. Coefficients are random integers that are independently and uniformly distributed over the segment from zero to some upper bound. The bound depends on the number of redundant binary solutions to the first equation that do not serve as solutions to the entire system. The proof uses the Schwartz - Zippel lemma. Moreover, if the first equation is linear, then there exists a pseudo-polynomial time algorithm to check the correctness of the reduction to the new equation in the general case.
Download file
Counter downloads: 153
- Title On binary solutions to systems of equations
- Headline On binary solutions to systems of equations
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 45
- Date:
- DOI 10.17223/20710410/45/3
Keywords
алгебраическое уравнение, вероятностный алгоритм, вычислительная сложность, algebraic equation, probabilistic algorithm, computational complexityAuthors
References
Seliverstov A. V. Binary solutions to some systems of linear equations // OPTA 2018. Communications in Computer and Information Science. V. 871. Cham: Springer, 2018. P. 183-192. https://doi.org/10.1007/978-3-319-93800-4_15
Схрейвер А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир, 1991. 344 с
Смолев В. В. Об одном подходе к решению булевого линейного уравнения с целыми положительными коэффициентами // Дискретная математика. 1993. Т. 5. № 3. С. 81-89
Gal A., Jang J.-T., Limaye N., et al. Space-efficient approximations for Subset Sum // ACM Trans. Computation Theory. 2016. V. 8. No. 4. Article 16. https://doi.org/10.1145/ 2894843
Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum // SODA'17 Proc. Twenty-Eighth Ann. ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: SIAM, 2017. P. 1073-1084
Koiliaris K. and Xu C. A faster pseudopolynomial time algorithm for subset sum // SODA'17 Proc. Twenty-Eighth Ann. ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: SIAM, 2017. P. 1062-1072
Bateni M. H., Hajiaghayi M. T., Seddighin S., and Stein C. Fast algorithms for knapsack via convolution and prediction // Proc. 50th Ann. ACM SIGACT Symp. on the Theory of Computing (STOC'18). N.Y.: ACM, 2018. P. 1269-1282. https://doi.org/10.1145/ 3188745.3188876
Curtis V. V. and Sanches C. A. A. An improved balanced algorithm for the subsetsum problem // Europ. J. Operat. Res. 2019. V. 275. P. 460-466. https://doi.org/10.1016/ j.ejor.2018.11.055
Cygan M., Mucha M., We˛grzycki K., and W lodarczyk M. On problems equivalent to (min,+)- convolution // ACM Trans. Algorithms. 2019. V. 15. No. 1. Article 14. https://doi.org/10. 1145/3293465
Kapovich I., 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. https://doi.org/10.1016/S0021-8693(03)00167-4
Рыбалов А. Н. О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема // Прикладная дискретная математика. 2017. № 37. С. 100-106
Рыбалов А. Н. О генерической NP-полноте проблемы выполнимости булевых формул // Прикладная дискретная математика. 2017. № 36. С. 106-112
Рыбалов А. Н. Релятивизованные генерические классы P и NP // Прикладная дискретная математика. 2018. № 40. С. 100-104
Lyubetsky V. A., Gershgorin R. A., and Gorbunov K. Yu. Chromosome structures: reduction of certain problems with unequal gene content and gene paralogs to integer linear programming // BMC Bioinformatics. 2017. V. 18. No. 40. https://doi.org/10.1186/ s12859-017-1944-x
Schwartz J. T. Fast probabilistic algorithms for verification of polynomial identities // J. ACM. 1980. V. 27. No. 4. P. 701-717. https://doi.org/10.1145/322217.322225
Bacher A., Bodini O., Hwang H.-K., and Tsai T.-H. Generating random permutations by coin-tossing: classical algorithms, new analysis, and modern implementation // ACM Trans. Algorithms. 2017. V. 13. No. 2. Article 24. https://doi.org/10.1145/3009909
On binary solutions to systems of equations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/3
Download full-text version
Counter downloads: 383