The concept of generic computational complexity has been extended to generalized register machines over an ordered field. In this case, the machine halts at every input and gives a meaningful answer at almost every input, but it can abandon the calculation using explicit notification, that is, there exists the vague halting state. Note that the machine does not make any error. A generic polynomial time algorithm is proposed to recognize systems of linear equations without any binary solution, when the number of equations m is close to the number of unknowns n. More precisely, two conditions are required. Firstly, the inequality 2n ≥(n-m+1)(n-m+2) holds. Such systems are called large because the number of equations is close to the number of unknowns. Secondly, some assumptions of generality of the system of equations are fulfilled. Our approach is based on finding a positive definite quadratic form among the set of forms that depend on parameters. On the other hand, a counterexample has been found, whicht shows the inapplicability of this method for checking the absence of any binary solution to one equation.
Download file
Counter downloads: 50
- Title Binary solutions to large systems of linear equations
- Headline Binary solutions to large systems of linear equations
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 52
- Date:
- DOI 10.17223/20710410/52/1
Keywords
binary solution, linear equation, generalized register machine, computational complexityAuthors
References
Mucha M., Nederlof J., Pawlewicz J., and Wegrzycki K. Equal-subset-sum faster than the meet-in-the-middle // 27th Ann. Europ. Symp. Algorithms, ESA 2019. Leibniz Intern. Proc. Informatics, LIPIcs. V. 144. Schloss Dagstuhl, Leibniz-Zentrum fur Informatik, 2019. Article 73.
Schroeppel R. and Shamir A. A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems // SIAM J. Computing. 1981. V. 10. No.3. P.456-464.
Bansal N., Gary S., Nederlof J., and Vyas N. Faster space-efficient algorithms for subset sum, k-sum, and related problems // SIAM J. Computing. 2018. V. 47. No. 5. P.1755-1777.
Grigoriev D. Complexity of Positivstellensatz proofs for the knapsack // Comput. Complexity. 2001. V.10. P.139-154.
Mucha M., Wegrzycki K., and Wlodarczyk M. A subquadratic approximation scheme for partition // Proc. Ann. ACM-SIAM Symp. Discrete Algorithms. Philadelphia: SIAM, 2019. P. 70-88.
Koiliaris K. and Xu C. Faster pseudopolynomial time algorithms for subset sum // ACM Trans. Comput. Theory. 2019. V. 15. No. 3. Article 40.
Curtis V. V., Sanches C. A. A. An improved balanced algorithm for the subset-sum problem // European J. Operational Res. 2019. V.275. P.460-466.
Схрейвер А. Теория линейного и целочисленного программирования. В 2-х т.М.: Мир, 1991. 702 с.
Селиверстов А. В. О двоичных решениях систем уравнений // Прикладная дискретная математика. 2019. №45. С. 26-32.
Goerdt A. and Lanka A. Recognizing more random unsatisfiable 3-SAT instances efficiently // Electronic Notes in Discrete Math. 2003. V. 16. P. 21-46.
Brown-Cohen J. and Raghavendra P. Extended formulation lower bounds for refuting random CSPs // Proc. ACM-SIAM Symp. Discrete Algorithms. Philadelphia: SIAM, 2020. P. 305-324.
Deshpande Y., Montanari A., O’Donnell R., et al. The threshold for SDP-refutation of random regular NAE-3SAT // Proc. Ann. ACM-SIAM Symp. Discrete Algorithms. Philadelphia: SIAM, 2019. P.2305-2321.
Neumann E. and Pauly A. A topological view on algebraic computation models // J. Complexity. 2018. V.44. P. 1-22.
Blum L., Shub M., and Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines // Bull. American Mathematical Society (N.S.). 1989. V.21. No. 1. P.1-46.
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. IX. Главные универсальные классы и Dis-пределы // Алгебра и логика. 2018. Т. 57. №6. С. 639-661.
Алаев П. Е., Селиванов В. Л. Поля алгебраических чисел, вычислимые за полиномиальное время. I // Алгебра и логика. 2019. Т. 58. №6. С. 673-705.
Алаев П. Е. Полиномиально вычислимые структуры с конечным числом порождающих // Алгебра и логика. 2020. Т. 59. №3. С. 385-394.
Коточигов А. М., Сучков А. И. Метод сокращения перебора в алгоритмах построения минимальных аддитивных цепочек // Компьютерные инструменты в образовании. 2020. №1. С. 5-18.
Селиверстов А. В. Симметричные матрицы, элементами которых служат линейные функции // Журн. вычислительной математики и математической физики. 2020. Т. 60. №1. С. 109-115.
Рыбалов А. Н. О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев // Прикладная дискретная математика. 2019. №44. С. 107-112.
Рыбалов А. Н. О генерической NP-полноте проблемы выполнимости булевых схем // Прикладная дискретная математика. 2020. № 47. С. 101-107.
Рыбалов А. Н. О генерической сложности проблемы представимости натуральных чисел суммой двух квадратов // Прикладная дискретная математика. 2020. №48. С. 93-99.
Рыбалов А. Н. О генерической сложности экзистенциальных теорий // Прикладная дискретная математика. 2020. №49. С. 120-126.
Harris J. and Tu L. W. On symmetric and skew-symmetric determinantal varieties // Topology. 1984. V. 23. No. 1. P.71-84.
Malaschonok G. and Scherbinin A. Triangular decomposition of matrices in a domain // LNCS. 2015. V. 9301. P.292-306.
Schwartz J.T. Fast probabilistic algorithms for verification of polynomial identities // J. ACM. 1980. V. 27. No. 4. P.701-717

Binary solutions to large systems of linear equations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 52. DOI: 10.17223/20710410/52/1
Download full-text version
Counter downloads: 147
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Telegram