# 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 ?
• Try reducing from 1-IN-3SAT. – Yuval Filmus Dec 14 '18 at 19:41
• @YuvalFilmus that is an answer. And my algorithm must be wrong. But why? – Solomonoff's Secret Dec 14 '18 at 19:49
• Your algorithm ignores the restriction that all variables be $\{0,1\}$. – Yuval Filmus Dec 14 '18 at 19:52
• @Solomonoff'sSecret The problem comes with free variables in the system. – GBat Dec 14 '18 at 20:22

## 1 Answer

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.