determine whether if a linear system has binary solutions.

91 Views Asked by At

Is there any general method that helps to determine a linear system have binary solutions?

E.g. For a linear system $$ Ax=b $$ Where $A \in \mathbb{N}^{m\times n}, b \in \mathbb{N}^{m\times 1}$. Is there any efficient way to determine if there is any solution fits this constraint $x \in \{0, 1\}^{n}$ ?

1

There are 1 best solutions below

3
On BEST ANSWER

No. This problem is a well-known NP-Complete problem. The best-known algorithms take time exponential in the size of the problem data. Unless P=NP (something that most computer scientists consider unlikely), there won't be an efficient polynomial-time algorithm for this problem.

This is problem MP1 in Garey and Johnson's Computers and Intractability (page 245.)