0
$\begingroup$

I'm wondering about systems of equations that take on a finite set of values for those variables. Is there a theory behind that? In particular, solving systems where the variable takes on values of either 0 or 1. The problem is probably NP-hard, but I'm wondering where to look to learn more about it.

Like for example,

$a^2 + bc - a = 0$

$b(a + d) - b = 0$

$c(a + d) - c = 0$

$d^2 + bc - d = 0$ where a, b, c, d are from {0, 1}.

  • 0
    Sounds like you are interested in 0-1 programming. You might start with http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns2012-12-08

1 Answers 1

0

Your system has a simple solution. Label the equations

[1] $a^2 + bc - a = 0$

[2] $b(a + d) - b = 0$

[3] $c(a + d) - c = 0$

[4] $d^2 + bc - d = 0$

Note that if $bc=1$ then equation [1] becomes $a^2+1-a=0$ which is false for $a=0,1$. Therefore one (or both) of $b,c$ is 0, and the term $bc$ drops out of equations [1] and [4], which become respectively $a(a-1)=0$ and $d(d-1)=0$ each of which is always true, so that the system reduces to only equations [2] and [3]. Either of these equations, given that one of $b,c$ is nonzero, implies that $a+d=1$, and furthermore $a+d=1$ implies that each of [2] and [3] hold, regardless of the values of $b,d$. Now if $b=c=0$ then $a,d$ can be any values, not just those satisfying $a+d=1$.

So the solution set can be expressed as:

$b=c=0$ and $a,d$ arbitrary, or

Exactly one of $b,c$ is $0$ and $a+d=1$.