反转二进制网络

如何反转二元方程，以便找到哪些输入将产生给定的输出。

Example:

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

矩阵形式：

1,1,0,1,0,0,0,0,0,1
0,1,0,1,1,0,0,0,0,1
0,1,1,0,0,1,0,0,0,1
1,0,0,1,0,0,0,0,0,1
0,1,0,1,1,0,0,0,0,1
0,0,0,0,0,1,0,0,0,1
0,0,0,1,0,0,1,0,0,1
0,0,0,1,1,0,1,1,0,1
0,0,0,0,0,1,0,0,1,1

附加限制：

• 主对角线始终为 1
• 我感兴趣的是是否有解决方案，而不是解决方案本身

我怎样才能通过算法找到输入 i0 -i8 以使输出 o0 - o8 为 1？我真正想知道是否有这样的解决方案。

我需要一种可扩展到更大网络的算法，至少最多 100 个输入/输出。

使用 XOR（而不是 OR），乍一看似乎某种形式的高斯-约尔消去法 http://en.wikipedia.org/wiki/Gauss%E2%80%93Jordan_elimination至少可以简化问题。改编自维基百科关于减少的文章中的伪代码行梯形 http://en.wikipedia.org/wiki/Row_echelon_form，我们得到：

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

这会将样本转换为：

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

从那里，您可以调整整数划分 http://en.wikipedia.org/wiki/Partition_(number_theory)算法生成一行的可能输入，同时考虑到先前行的分区。生成分区是记忆化的一个很好的选择。

还是需要做一下时序分析，看看上面的做法是否值得。