The nice thing about binary numbers (a = 0 or 1) is that a^b = a for all values of b > 0. So your "nonlinear" equation will become linear by the simple exploit of getting rid of all polynomial terms.
When you have a number of linear equations, the problem becomes: what combination of the coefficients (I am assuming the coefficients are linear) gives me the constant term for this equation? In principle you should be able to eliminate two variables (since you have three equations) and end up with just a single equation. Any combination of 1's and 0's that satisfies this will now be a solution to your problem. You would have to look at the coefficients - is there a single one that is equal to the constant? Then you have your answer (that bit = 1, all the others are 0). Or is there a pair of coefficients that add up to the constant? As you start to combine more terms, the number of permutations to test for gets rapidly larger. I can't think of a "clever" way to get beyond this - you would have to take a look at the coefficients (for example, if two variables have the same coefficient you can reduce your problem accordingly).
UPDATE Given the example
x1 + x2 + x3 + x4 + x5 = s
x1x2 + x2x3 + x3x4 + x4x5 = t
We can notice the following:
- the number of bits set to
1
must be == 5 (from the first equation)
- t must be < s (since no new terms appear, and we have products of terms)
In a toy example like this we can actually do an exhaustive search. When the number of terms gets much larger, the size of s
and t
will drive the complexity. A few things to note
Number of possible combinations of n bits summing to s = n!/(n-s)!s!
. And it would be worth factoring the "compound" equation, using factors that appear most frequently as common terms. In the above, you would look at
x2(x1+x3) + x4(x3+x5) = t
Now we can see that if t > 2, we must have both x2=1
and x4=1
; similar simplifications may be possible elsewhere.
Since you actually have only three equations, I would look for ways to set the largest possible number of elements to zero (using an approach like the above), then do an exhaustive search with the ones that are left...