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

15

Предположим, нам дан набор из 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) интересен. Кто-нибудь знает о сложности (сложности аппроксимации) для этого вопроса?

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

Мухаммед Р. Салаватипур
источник

Ответы:

18

Это 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 , n({1,,n},E)m=|E|m×(n+1)AA[i,j]=1j<n+1(i,j)E . Другими словами, при п + 1 переменных х 1 , ... , х п + 1 , мы хотим вычислить т линейные формы х я + х J + х п + 1 для всех ( я , J ) E .A[i,n+1]=1n+1x1,,xn+1mxi+xj+xn+1(я,J)Е

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

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

Райан Уильямс
источник
Спасибо Райан. Действительно актуальная статья. Я подумал, может ли проблема быть такой же сложной, как покрытие вершин в гиперграфах, по крайней мере, в том случае, если вы не хотите генерировать большие суммы XOR (я думаю, что в этой статье говорится об отсутствии отмены).
Мохаммад Р. Салаватипур
3
Для случая без отмены, NP-твердость отмечена в Garey-Johnson под несколько неясным названием «Ensemble Computing» (задача PO9, в A11.1). Сокращение фактически совпадает с приведенным Райаном, см. Раздел 3.2.2 в ГДж.
Янне Х. Корхонен