Scholarlink

Abstract <p>We consider the problem of finding a binary solution to a system of linear equations modulo three. In the case where the number of equations is less than a sufficiently slowly growing function of the number of variables, a new polynomial-time algorithm is proposed to recognize the existence of a binary solution to such a system. The algorithm is based on the note that, if the coefficient matrix contains nonzero columns proportional to each other, then the elimination of the corresponding variables preserves the property of having no binary solution to the system. In particular, every system of two equations in five variables permits the elimination of some variables that preserves the property of having no binary solution to the system. Based on these results, we propose an errorless heuristic algorithm, which is implemented in the Python programming language. The NumPy library is used to represent matrices and perform basic operations. The input is the augmented matrix of the system. The empirical runtime estimate is calculated using the implementation. It&#xa0;is experimentally shown that the algorithm is more efficient for sparse systems of equations. Obviously, the binary search method can find a binary solution to the system when one exists. This observation opens up the possibility of its practical use, in particular, for solving problems of mathematical biology.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Binary Solutions to a System of Linear Equations Modulo Three

  • 期刊论文

  • 发表日期：

    2025年3月25日

查看全文
  • O. A. Zverkov,
  • A. V. Seliverstov

摘要

Abstract

We consider the problem of finding a binary solution to a system of linear equations modulo three. In the case where the number of equations is less than a sufficiently slowly growing function of the number of variables, a new polynomial-time algorithm is proposed to recognize the existence of a binary solution to such a system. The algorithm is based on the note that, if the coefficient matrix contains nonzero columns proportional to each other, then the elimination of the corresponding variables preserves the property of having no binary solution to the system. In particular, every system of two equations in five variables permits the elimination of some variables that preserves the property of having no binary solution to the system. Based on these results, we propose an errorless heuristic algorithm, which is implemented in the Python programming language. The NumPy library is used to represent matrices and perform basic operations. The input is the augmented matrix of the system. The empirical runtime estimate is calculated using the implementation. It is experimentally shown that the algorithm is more efficient for sparse systems of equations. Obviously, the binary search method can find a binary solution to the system when one exists. This observation opens up the possibility of its practical use, in particular, for solving problems of mathematical biology.