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

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, privacy policy and cookie policy

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