On binary solutions to systems of equations

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.