Инвертирующие двоичные сети

Question

Как я могу инвертировать бинарное уравнение, чтобы я мог найти, какие входы будут производить данный вывод.

Пример:

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 входов / выходов.

Answer 1

При использовании XOR (а не OR) на первый взгляд кажется, что некоторая форма исключения Гаусса – Иордана может, по крайней мере, упростить проблему. Адаптируя псевдокод из статьи в Википедии об уменьшенной форме ряда строк , мы получаем:

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

Оттуда вы можете адаптировать алгоритм целочисленного разбиения , чтобы сгенерировать возможные входные данные для строки, принимая во внимание разделы для предыдущих строк. Создание раздела является отличным кандидатом на запоминание.

Еще нужно провести анализ времени, чтобы понять, стоит ли вышеупомянутое.

Answer 2

Одна интересная вещь о xor заключается в том, что:

a ^ b ^ b = a

Это позволяет делать приятные манипуляции, скажем, у вас есть:

a ^ b = c

Тогда вы можете легко вычислить a с помощью xor с обеих сторон с помощью b, получив:

a = c ^ b

Если бы я был на вашем месте, я бы использовал этот трюк для получения входных данных от выходов. Символ and, который появляется в ваших уравнениях, имеет эффект , удаляя некоторые входные переменные из некоторых уравнений, поэтому он не представляет проблемы для этого подхода.

Во-первых, вы должны знать, что может не быть решением для конкретных матриц коэффициентов , например, если входные данные никогда не появляются ни в одном уравнении (то есть столбец из всех нулей матрица), или если уравнение появляется дважды (то есть две одинаковые строки), или если уравнение является комбинацией двух других уравнений.

Теперь, предполагая, что матрица, которую вы имеете , дает решение вашей проблемы, подход будет использовать каждое уравнение, чтобы найти один из входных данных. Для каждого уравнения xor обе стороны для всех входов, кроме одного входа (и варьировать этот вход для каждого уравнения). Например, предположим, что я хочу использовать первое уравнение для поиска i0, а второе для поиска i1 (обратите внимание, что для получения этого значения в уравнении должен появиться ввод), у меня теперь будет:

i0 = o0 ^ i1 ^ i3
i1 = o1 ^ i3 ^ i4

Продолжите для других уравнений, затем замените все входные данные на правой стороне их значениями из уравнений. Повторите рекурсивно, пока правая сторона не содержит только выходы. Если вы повторите для всех уравнений, вы найдете значения всех входных данных.

Я уверен этот подход можно оптимизировать, используя уже установленные методы решения линейной системы уравнений, особенно с использованием матричной формы.

Answer 3

Вы можете решить проблему 2-SAT за полиномиальное время, см. здесь .

Вот ссылка на бумагу с быстрым алгоритмом (тяжелая математика, я буду искать лучшую ссылку).

Другая ссылка с тяжелой математикой и псевдокодом .

Редактировать: Хотя я нашел много статей по этому вопросу, я не увидел много реализуемого кода. Большая часть работы была на доказательство удовлетворенности. Вам, вероятно, придется упростить предложения (удаляйте те, которые имеют нули в каждом прогоне), затем использовать рекурсивный алгоритм, чтобы доказать неуязвимость, и если вы обнаружите, что он был удовлетворен, то вы его решили.