# javascript - Inverting binary networks

How can I invert a binary equation, such that I can find which inputs will produce a given output.

Example:

``Inputs: i0 through i8Outputs: o0 through o8Operators: ^ = XOR, & = AND``

Binary equations:

``(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:

``1,1,0,1,0,0,0,0,0,10,1,0,1,1,0,0,0,0,10,1,1,0,0,1,0,0,0,11,0,0,1,0,0,0,0,0,10,1,0,1,1,0,0,0,0,10,0,0,0,0,1,0,0,0,10,0,0,1,0,0,1,0,0,10,0,0,1,1,0,1,1,0,10,0,0,0,0,1,0,0,1,1``

• The prime diagonal is always 1
• I am interested if there is a solution or not, more then the solution itself

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
rowCount := the number of rows in M
columnCount := the number of columns in M
for 0 ≤ r < rowCount do
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
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
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 `a` by `xor`ing both sides with `b`, getting:

``````a = c ^ b
``````

If I was in your place, I'd use this trick to get the input from the outputs. The `and`ing 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.