Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2021, Number 52, Pages 5–15
DOI: https://doi.org/10.17223/20710410/52/1
(Mi pdm735)
 

This article is cited in 9 scientific papers (total in 9 papers)

Theoretical Backgrounds of Applied Discrete Mathematics

Binary solutions to large systems of linear equations

A. V. Seliverstov

Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, Russia
Full-text PDF (662 kB) Citations (9)
References:
Abstract: 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.
Keywords: binary solution, linear equation, generalized register machine, computational complexity.
Funding agency Grant number
Russian Foundation for Basic Research 18-29-13037
Bibliographic databases:
Document Type: Article
UDC: 519.161
Language: Russian
Citation: A. V. Seliverstov, “Binary solutions to large systems of linear equations”, Prikl. Diskr. Mat., 2021, no. 52, 5–15
Citation in format AMSBIB
\Bibitem{Sel21}
\by A.~V.~Seliverstov
\paper Binary solutions to large systems of linear equations
\jour Prikl. Diskr. Mat.
\yr 2021
\issue 52
\pages 5--15
\mathnet{http://mi.mathnet.ru/pdm735}
\crossref{https://doi.org/10.17223/20710410/52/1}
Linking options:
  • https://www.mathnet.ru/eng/pdm735
  • https://www.mathnet.ru/eng/pdm/y2021/i2/p5
  • This publication is cited in the following 9 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:211
    Full-text PDF :73
    References:29
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024