Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time.

Additionally, all of the coefficients of $A$ are in $\{-1, 0, 1\}$, but I couldn't find a way to use that.

The trivial case is if the (matrix $A$ of the) system is invertible, there is only one solution, it is easy to check whether all of them belong to $\{0,1\}$.

However, if you have infinitely many solutions, and $k$ free variable, I can't find a way to do better than check all the $2^k$ possibilities.


Do you know any algorithm to do so in polynomial time ?


I also tried to do a reduction from SAT (or some variant with n clauses and n variables in each clause, to show that it is NP complete), but because of the fact that we have $Ax = b$ and not $Ax \geq b$, I couldn't do that either.


Do you have a reduction to show that this problem is NP complete ?
1-IN-3SAT is the following problem: given a collection of 3-clauses (just like 3SAT), decide whether there is a truth assignment which satisfies exactly one literal in each clause. 1-IN-3SAT is known to be NP-complete, see for example here. You can reduce 1-IN-3SAT to your problem – I'll let you work out the details.