Binary solutions to large systems of linear equations

A. V. Seliverstov

Prikladnaâ diskretnaâ matematika, no. 2 (2021), pp. 5-15.

Résumé

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\geqslant (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.

Détail

Keywords: binary solution, linear equation, generalized register machine, computational complexity.

Bibliographie

[1] Schrijver A., Theory of linear and integer programming, John Wiley Sons, New York, 1986

[2] Seliverstov A. V., “On binary solutions to system of equations”, Prikladnaya Diskretnaya Matematika, 2019, no. 45, 26–32 (in Russian)

[3] Koiliaris K., Xu C., “Faster pseudopolynomial time algorithms for subset sum”, ACM Trans. Comput. Theory, 15:3 (2019), 40

[4] Curtis V. V., Sanches C. A. A., “An improved balanced algorithm for the subset-sum problem”, European J. Operational Res., 275 (2019), 460–466

[5] Mucha M., Węgrzycki K., Włodarczyk M., “A subquadratic approximation scheme for partition”, Proc. Ann. ACM-SIAM Symp. Discrete Algorithms, SIAM, Philadelphia, 2019, 70–88

[6] Schroeppel R., Shamir A., “A $T=O(2^{n/2})$, $S=O(2^{n/4})$ algorithm for certain NP-complete problems”, SIAM J. Computing, 10:3 (1981), 456–464

[7] Bansal N., Garg S., Nederlof J., Vyas N., “Faster space-efficient algorithms for subset sum, k-sum, and related problems”, SIAM J. Computing, 47:5 (2018), 1755–1777

[8] Grigoriev D., “Complexity of Positivstellensatz proofs for the knapsack”, Comput. Complexity, 10 (2001), 139–154

[9] Mucha M., Nederlof J., Pawlewicz J., Węgrzycki K., “Equal-subset-sum faster than the meet-in-the-middle”, 27th Ann. Europ. Symp. Algorithms, ESA 2019, Leibniz Intern. Proc. Informatics, LIPIcs, 144, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2019, 73

[10] Goerdt A., Lanka A., “Recognizing more random unsatisfiable 3-SAT instances efficiently”, Electronic Notes in Discrete Math., 16 (2003), 21–46

[11] Brown-Cohen J., Raghavendra P., “Extended formulation lower bounds for refuting random CSPs”, Proc. ACM-SIAM Symp. Discrete Algorithms, SIAM, Philadelphia, 2020, 305–324

[12] 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, SIAM, Philadelphia, 2019, 2305–2321

[13] Neumann E., Pauly A., “A topological view on algebraic computation models”, J. Complexity, 44 (2018), 1–22

[14] Blum L., Shub M., 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.), 21:1 (1989), 1–46

[15] Daniyarova E. Yu., Myasnikov A. G., Remeslennikov V. N., “Algebraic geometry over algebraic structures. IX. Principal universal classes and Dis-limits”, Algebra and Logic, 57:6 (2019), 414–428

[16] Alaev P. E., Selivanov V. L., “Fields of algebraic numbers computable in polynomial time. I”, Algebra and Logic, 58:6 (2020), 447–469

[17] Alaev P. E., “Polynomially computable structures with finitely many generators”, Algebra and Logic, 59:3 (2020), 266–272

[18] Kotochigov A. M., Suchkov A. I., “A method for reducing iteration in algorithms for building minimal additive chains”, Komp'yuternye Instrumenty v Obrazovanii, 2020, no. 1, 5–18 (in Russian)

[19] Seliverstov A. V., “Symmetric matrices whose entries are linear functions”, Comput. Math. and Math. Physics, 60:1 (2020), 102–108

[20] Rybalov A. N., “On generic undecidability of Hilbert's tenth problem for polynomial trees”, Prikladnaya Diskretnaya Matematika, 2019, no. 44, 107–112 (in Russian)

[21] Rybalov A. N., “On generic NP-completeness of the problem of Boolean circuits satisfiability”, Prikladnaya Diskretnaya Matematika, 2020, no. 47, 101–107 (in Russian)

[22] Rybalov A. N., “On generic complexity of the problem of representation of natural numbers by sum of two squares”, Prikladnaya Diskretnaya Matematika, 2020, no. 48, 93–99 (in Russian)

[23] Rybalov A. N., “On generic complexity of the existential theories”, Prikladnaya Diskretnaya Matematika, 2020, no. 49, 120–126 (in Russian)

[24] Harris J., Tu L. W., “On symmetric and skew-symmetric determinantal varieties”, Topology, 23:1 (1984), 71–84

[25] Malaschonok G., Scherbinin A., “Triangular decomposition of matrices in a domain”, LNCS, 9301, 2015, 292–306

[26] Schwartz J. T., “Fast probabilistic algorithms for verification of polynomial identities”, J. ACM, 27:4 (1980), 701–717