ansaurus

Question

Answer 1

+4 A:

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

Sinan Taifour 2009-08-08 07:25:35

It appears my answer was a much lower level than that expected/required. Sorry ~!

Sinan Taifour 2009-08-08 07:31:41

Actually this is pretty good. It's about where I'm at. Basically I am trying to implement Gussian elimination for this. But somehow it is breaking down with the two different implementations I've tried so far.

Killroy 2009-08-08 08:24:02

nice answer! :)

Charles Ma 2009-08-08 09:44:02

I've only accepted the other answer, since he provided pseudo code, which is what I wanted. But what you said about XOR pointed me in the right direction and let me figure it out. Thanks!

Killroy 2009-08-08 12:20:36

You're welcome :) If I was in your place I'd accept his answer too. +1 to him from me!

Sinan Taifour 2009-08-08 21:54:35

Answer 2

A:

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.

Lance Roberts 2009-08-08 07:25:50

Answer 3

+5 A:

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.

outis 2009-08-08 09:34:56

Hey, I've just come to a similar state. Basically I figured the only elementary row operation that makes sense is to XOR rows together. But then I got that row of 0s and thought that won't work. Now I realize there still can be multiple solutions, and therefore I can get free variables. So all I can do is reduce it as much as possible and then try all the possible inputs for the 0 rows. Thanks!

Killroy 2009-08-08 10:35:38

ansaurus

tags:

views:

answers:

Inverting binary networks

related questions