наименьший размер цепи с использованием вентилей XOR

Предположим, нам дан набор из n булевых переменных x_1, ..., x_n и набора из m функций y_1 ... y_m, где каждый y_i является XOR (заданного) подмножества этих переменных. Цель состоит в том, чтобы вычислить минимальное количество операций XOR, которое необходимо выполнить для вычисления всех этих функций y_1 ... y_m.

Обратите внимание, что результат операции XOR, скажем, x_1 XOR x_2 может использоваться при вычислении нескольких значений y_j, но считается одним. Кроме того, обратите внимание, что может быть полезно вычислить XOR из гораздо большей коллекции x_i (больше, чем любая функция y_i, например, вычисление XOR всех x_i) для более эффективного вычисления y_i,

Эквивалентно, предположим, что у нас есть двоичная матрица A и вектор X, и цель состоит в том, чтобы вычислить вектор Y так, чтобы AX = Y, где все операции выполнялись в GF (2) с использованием минимального количества операций.

Даже когда каждый ряд А имеет ровно k, каждый (скажем, k = 3) интересен. Кто-нибудь знает о сложности (сложности аппроксимации) для этого вопроса?

Мухаммед Салаватиопур

Это NP-хард. См .: Джоан Бояр, Филипп Мэтьюз, Рене Перальта. Методы минимизации логики с приложениями к криптологии. http://link.springer.com/article/10.1007/s00145-012-9124-7

Сокращение от Vertex Cover очень хорошее.

Дан граф с m = | E | определите матрицу A m × ( n + 1 ) как: A [ i , j ] = 1, если j < n + 1 и ( i , j ) ∈ E , и A [ i , $(\{1,\ldots,n\},E)$$m=|E|$$m \times (n+1)$$A$$A[i,j] = 1$$j < n+1$$(i,j) \in E$ . Другими словами, при п + 1 переменных х 1 , ... , х п + 1 , мы хотим вычислить т линейные формы х я + х J + х п + 1 для всех ( я , J ) ∈ E .$A[i,n+1] = 1$$n+1$$x_1,\ldots,x_{n+1}$$m$$x_i+x_j+x_{n+1}$$(i,j) \in E$

Небольшое размышление показывает, что существует схема XOR для с затворами с веером два, вычисляющая линейное преобразование A только с затворами m + k , где k - оптимальное покрытие вершин для графа. (Сначала вычислите x i ′ + x n + 1 для всех i ′ в покрытии вершин, используя k операций. Затем все линейные формы вычисляются еще в m операциях.) Оказывается, что это также схема минимального размера!$A$$A$$m+k$$k$$x_{i'} + x_{n+1}$$i'$$k$$m$

Доказательство того, что сокращение является правильным, не так приятно. Я хотел бы увидеть краткое доказательство того, что это сокращение является правильным.