How can I invert a binary equation, such that I can find which inputs will produce a given output.
Inputs: i0 through i8
Outputs: o0 through o8
Operators: ^ = XOR, & = AND
(1&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o0
(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o1
(0&i0) ^ (1&i1) ^ (1&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o2
(1&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o3
(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o4
(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o5
(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (1&i6) ^ (0&i7) ^ (0&i8) = o6
(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (1&i6) ^ (1&i7) ^ (0&i8) = o7
(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (1&i8) = o8
In matrix form:
How can I, algorithmically find inputs i0 -i8 such that outputs o0 - o8 are 1? What I really want to find is if there is such a solution or not.
I need an algorithm which is scalable to larger networks, at least up to 100 inputs/outputs.
With XOR (rather than OR), it seems at first glance that some form of Gauss–Jordan elimination can at least simplify the problem. Adapting the pseudocode from the Wikipedia article on reduced row echelon form, we get:
function ToReducedRowEchelonForm(Matrix M) is // 'lead' is the column index in a row of the leading 1 lead := 0 rowCount := the number of rows in M columnCount := the number of columns in M for 0 ≤ r < rowCount do if columnCount ≤ lead then stop end if i = r // Find row with lead point while M[i, lead] = 0 do i = i + 1 if rowCount = i then // no pivot in this column, move to next i = r lead = lead + 1 if columnCount = lead then stop end if end if end while Swap rows i and r for 0 ≤ i < rowCount do if i ≠ r do Set row i to row i XOR row r end if end for lead = lead + 1 end for end function
This converts the sample to:
1,0,0,0,0,0,0,1,0,0 0,1,0,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,0,1,0,0,0,1,0,1 0,0,0,0,1,0,0,1,0,0 0,0,0,0,0,1,0,0,0,1 0,0,0,0,0,0,1,1,0,0 0,0,0,0,0,0,0,0,1,0 0,0,0,0,0,0,0,0,0,0
From there, you could adapt an integer partitioning algorithm to generate the possible inputs for a row, taking in to account the partitions for previous rows. Generating a partition is a great candidate for memoization.
Still need to do a timing analysis to see if the above is worthwhile.
One interesting thing about
xor is that:
a ^ b ^ b = a
This allows for nice manipulations, let's say you have:
a ^ b = c
Then you can easily figure out
xoring both sides with
a = c ^ b
If I was in your place, I'd use this trick to get the input from the outputs. The
anding that appears in your equations only have the effect of removing some input variables from some equations, so it poses no problem to this approach.
First off, you must know, there might not be a solution for particular coefficient matrices, for example, if the input never appears in any equation (that is, a column of all-zeros in the matrix), or if an equation appears twice (that is, two identical rows), or if an equation is a combination of two other equations.
Now, assuming the matrix you have does yield a solution to your problem, the approach would be use each equation to find one of the inputs. For each equation,
xor both sides for all the inputs except one input (and varry this input for each equation). For example, let's say I want to use the first equation to find
i0 and the second to find
i1 (notice the input has to appear in the equation to make this value), I would now have:
i0 = o0 ^ i1 ^ i3 i1 = o1 ^ i3 ^ i4
Continue for the other equations, then substitute all inputs on the right side with their values from the equations. Repeat recursively till the right side only contains outputs. If you repeat for all equations, you'll find the values of all inputs.
I am sure this approach can be optimized using already-established methods in solving a linear system of equations, especially utilizing the matrix form.
You can solve the 2-SAT problem in polynomial time, see here.
Here's the link to a paper with a fast algorithm (heavy math I'll keep looking for a better link).
Another link with heavy math and pseudocode.
Edit: While I found many papers on this I didn't see much implementable code. Most of the work was on proving satisfiability. You'll probably have to streamline the clauses (remove the ones with zeroes on each run), then use a recursive algorithm to prove unsatifiability, and if you find you've satifisfied it, then you've solved it.