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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.