Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}.

share|improve this question
can't you just try all alternatives? 2^4 isn't that big number. –  tp1 Dec 8 '12 at 9:22
Sounds like you are interested in 0-1 programming. You might start with en.wikipedia.org/wiki/Linear_programming#Integer_unknowns –  Gerry Myerson Dec 8 '12 at 11:49

1 Answer 1

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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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