Решите, содержит ли ядро матрицы ненулевой вектор, все записи которого равны -1, 0 или 1

Даны $m$ от $n$ двоичной матрицы $M$ (записи являются $0$ или $1$ ), проблема в том , чтобы определить, существует два двоичных векторов $v_1 \ne v_2$ таким образом, что $Mv_1 = Mv_2$ (все операции , выполняемые над $\mathbb{Z}$ ). Эта проблема NP-сложная?

Это ясно в NP, поскольку вы можете дать два вектора в качестве свидетелей.

Эквивалентно: если дано $M$ , существует ли ненулевой вектор $v\in \{-1,0,1\}^n$ такой, что $Mv=0$ ?

Эквивалентно: С учетом $n$ векторов $X=\{x_1,\dots,x_n\}$ над $\{0,1\}^m$ , существуют два различных подмножества такое , что ? $A,B \subseteq X$ $\sum_{x \in A} x = \sum_{x \in B} x$

cc.complexity-theory np-hardness linear-algebra Мухаммед Аль-Туркистани
источник

Если я не понимаю вопрос, разве это не эквивалентно определению, существует ли ненулевой

v

$v$ такой, что

M v = 0

$Mv = 0$ ? И разве это не решается путем определения ранга

M

$M$ ?

mhum

@mhum нет, это эквивалентно определению, существует ли ненулевой

v \in {- 1, 0, 1}^{n}

$v \in \{-1, 0, 1\}^n$ такой, что

M v = 0

$Mv = 0$ .

Сашо Николов

Ах. Я пропустил , что

v_{i}

$v_i$ также должен был быть двоичным. Моя ошибка.

mhum

Похоже, проблема выполнимости для 0/1-целочисленного программирования. Операции над

Z

$\mathbb{Z}$ или над

Z_{2}

$\mathbb{Z_2}$ ?

Каве

Переформулировка задачи: для заданных

n

$n$ векторов

X = {x_{1}, \dots, x_{n}}

$X = \{ x_1,\dots,x_n \}$ более

{0, 1}^{m}

$\{ 0,1 \}^m$ . Существуют ли два разных подмножества

A, B \subseteq X

$A,B \subseteq {X}$ , для которых

\sum_{x \in A} x = \sum_{x \in B} x

$\sum_{x \in A} x = \sum_{x \in B} x$ ? Я думаю, что более вероятно, что NP-сложнее, если суммы не взяты по модулю два, то есть операции над

Z

$\mathbb{Z}$

Джон Д.

Ответы:

Я использую эквивалентную формулировку user17410:

Вход: векторов над , является частью входного вопроса. Вопрос: Существуют ли два разных подмножества таких что $n$ $X = \{ x_1, \dots, x_m \}$ $\{0,1\}^n$ $n$
$A,B \subseteq X$

\sum_{x \in A} x = \sum_{x \in B} x

$\sum_{x \in A} x = \sum_{x \in B} x$

Доказательство твердости включает в себя множество промежуточных сокращений, которые следуют той же «цепочке», используемой для доказательства твердости стандартной задачи EQUAL SUBSET SUM:

X3C подмножество SUM РАЗДЕЛА четный-нечетный РАЗДЕЛА РАВНО SUBSET СУММА $\leq$ $\leq$ $\leq$ $\leq$

(Я все еще проверяю это, так что это может быть неправильно :)

ШАГ 1

$X = \{ x_1, \dots, x_m \}$ $x_i$ $\{0,1\}^n$ $t$ $A \subseteq X$

\sum_{x \in A} x = t

$\sum_{x \in A} x = t$

n

$n$

Y = {y_{1}, . . ., y_{n}}

$Y = \{y_1,...,y_n\}$

C

$C$

m

$m$

C = {C_{1}, . . ., C_{m}}

$C = \{C_1,...,C_m\}$

x_{i} [j] = 1

$x_i[j] = 1$

j

$j$

C_{i}

$C_i$

t = [1, 1, . . .1]

$t = [1,1,...1]$

$A,B$ $m$ $\{0,1\}^n$ $A,B$ $x_1 ... x_m$ $max\{x_i\} = O((mn)^k)$ $k$

Например, набор векторов:

x1 2 1 0 1
x2 1 2 3 1

Эквивалентно 0-1 векторам:

x1  1 1 0 1   1 0   0 0 0
    1 0 0 0   0 1   0 0 0 
    0 0 0 0   1 1   0 0 0 
              ^ ^
                +-- 0 elsewhere

x2  1 1 1 1   0 0   1 0 0
    0 1 1 0   0 0   0 1 0
    0 0 1 0   0 0   0 0 1
    0 0 0 0   0 0   1 1 1
                    ^ ^ ^
                      +-- 0 elsewhere

$A$ $A$ $B$ $mn$

Таким образом, следующая проблема является NP-полной.

ШАГ 3

$B = \{ x_1, \dots, x_m \}$ $x_i$ $\{0,1\}^n$ $X$ $B_1, B_2$

\sum_{x \in B_{1}} x = \sum_{x \in B_{2}} x

$\sum_{x \in B_1} x = \sum_{x \in B_2} x$

$X = \{ x_1, \dots, x_m \}$ $t$ $S = \sum x_i$ $X$ $b' = -t + 2S$ $b'' = t + S\;$ $B = X \cup \{b',b''\}$

( ) Предположим, что существует такой, что ; мы устанавливаем и ; мы имеем $\Rightarrow$ $A \subseteq X$ $\sum_{x \in A} x= t$ $B_1 = A \cup \{b'\}$ $B_2 =B \setminus B_1 = X \setminus \{A\} \cup \{b''\}$

\sum_{x \in B_{1}} = b^{'} + \sum_{x \in A} x = t - t + S = 2 S

$\sum_{x \in B_1} = b'+\sum_{x \in A} x = t - t + S = 2S$

\sum_{x \in B_{2}} = b^{″} + \sum_{x \in X ∖ A} x = b^{″} + S - \sum_{x \in A} x = 2 S

$\sum_{x \in B_2} = b'' + \sum_{x \in X\setminus A} x = b'' + S - \sum_{x \in A} x=2S$

( ) Предположим, что и имеют равную сумму. не могут оба принадлежать одному и тому же набору (в противном случае их сумма равна и не может быть "сбалансирована" элементами в другом наборе). Предположим, что ; у нас есть: $\Leftarrow$ $B_1$ $B_2$ $b', b''$ $\geq 3S$ $b' = -t + 2S \in B_1$

- t + 2 S + \sum_{x \in B_{1} ∖ {b^{'}}} x = t + S + \sum_{x \in B_{2} ∖ {b^{″}}} x

$-t +2S+ \sum_{x \in B_1 \setminus\{b'\}} x = t + S + \sum_{x \in B_2 \setminus\{b''\}} x$

Следовательно, мы должны иметь а является правильным решением для 0-1 VECTOR SUM. $\sum_{x \in B_1 \setminus\{b'\}} x = t$ $B_1 \setminus\{b'\}$

Мы допускаем только 0-1 векторов в множестве , поэтому векторы должны быть «представлены в унарном виде», как показано в ШАГЕ 2. $B$ $b', b''$

ШАГ 3

Проблема по-прежнему NP-полная, если векторы нумеруются из и два подмножества должны иметь одинаковый размер, и мы требуем, чтобы содержал ровно один из для (таким образом, из-за ограничения равного размера, другой элемент пары должен быть включен в ) ( 0-1 ВЕКТОР-ДАЖЕ-РАЗДЕЛЕНИЕ РАЗДЕЛА ). $x_1,...,x_2n$ $X_1,X_2$ $X_1$ $x_{2i-1},x_{2i}$ $1 \leq i \leq n$ $X_2$

Доказательство:: Сокращение от 0-1 VECTOR PARTITION и аналогично уменьшению от PARTITION к EVEN-ODD PARTITION. Если - это векторов более замените каждый вектор двумя векторами более : $X = \{x_1,...,x_m\}$ $m$ $\{0,1\}^n$ $\{0,1\}^{2n+2m}$

       1   2       n
 --------------------
 x_i  b_1 b_2 ... b_n

 becomes:

           1 2 ... 2i ... 2m
  --------------------------
  x'_2i-1  0 0 ...  1 ...  0  b_1 b_2 ... b_n   0   0  ...  0  
  x'_2i    0 0 ...  1 ...  0   0   0  ...  0   b_1 b_2 ... b_n

Из-за элемента векторы и не могут содержаться в одном и том же подмножестве; и правильное решение 0-1 ВЕКТОРНОГО РАЗДЕЛА ВЕКТОРА соответствует действительному решению исходного 0-1 ВЕКТОРНОГО РАЗДЕЛА (просто выберите элементы 2m + 1..2m + n каждого вектора решения, отбрасывая векторы, которые содержат все нули в этих позициях). $2i$ $x'_{2i-1}$ $x'_{2i}$

ШАГ 4

0-1 ВЕКТОРНАЯ РАВНОВЕСНАЯ СУБСЕТНАЯ СУММА (проблема в вопросе) является NP-полной: сокращение от 0-1 ВЕКТОРНОГО РАЗДЕЛЕНИЯ ДАЖЕ-СТОЛБОВ аналогично сокращению от СОБСТВЕННОГО РАЗДЕЛЕНИЯ ДАЖЕ К ОБРАЗНОЙ СУБСЕТЕ, что доказано Герхардом Дж. Вёгингером , Zhongliang Ю., о проблеме равного подмножества суммы : дан упорядоченное множество из векторов над , мы строим множество из векторов над . $A = \{x_1,...,x_{2m}\}$ $2m$ $\{0,1\}^n$ $Y$ $3m$ $\{0,1\}^{2m+n}$

Для каждого вектора мы строим вектор над следующим образом: $x_{2i-1}, 1 \leq i \leq m$ $y_{2i-1}$ $\{0,1\}^{2m+n}$

  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  0 0 ... 2  0  ... 0   0   0       1       0  x_{2i-1}

Для каждого вектора мы строим вектор над следующим образом: $x_{2i}, 1 \leq i \leq m-1$ $y_{2i}$ $\{0,1\}^{2m+n}$

  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  0 0 ... 0  2  ... 0   0   0       1       0  x_{2i}

Мы отображаем элемент в $x_{2m}$

  1 2 ...       ... m  m+1 m+2 ...  . 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  2 0 ...       ... 0   0   0          1  x_{2m}

Наконец, мы добавляем фиктивных элементов: $m$

  1 2 ...       ... m  m+1 m+2 ...  ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  4 0 ...       ... 0   0   0            0  0    ... 0
  0 4 ...       ... 0   0   0            0  0    ... 0
  ...
  0 0 ...       ... 4   0   0            0  0    ... 0

Еще раз отметим, что векторы, содержащие значения могут быть представлены «унарно» с использованием группы из 0-1 векторов, как показано в ШАГЕ 2. $> 1$

$Y$ имеет два непересекающихся подмножества имеющих равную сумму тогда и только тогда, когда имеет четно-нечетное разбиение. $Y_1,Y_2$ $X$

Марцио де Биаси
источник

то, что вы называете векторным разбиением 0-1, эквивалентно проблеме определения, имеет ли система множеств несоответствие 0. Это NP сложная задача, поскольку она охватывает, например, проблему расщепления 2-2 множеств, см. thm 9 в этой статье guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps ; В моей статье есть немного больше о твердости расхождений. paul.rutgers.edu/~anikolov/Files/charikarM.pdf

Сашо Николов

Я также считаю, что вы неправильно сформулировали проблему четно-нечетного разбиения. если никакие два последовательных вектора не могут быть в одном наборе, проблема тривиальна. я полагаю, вы имеете в виду, что требуется для всех и

| X_{i} \cap {x_{2 j - 1}, x_{2 j}} | = 1

$|X_i \cap \{x_{2j-1}, x_{2j}\}| = 1$

i \in {1, 2}

$i \in \{1, 2\}$

1 \leq j \leq m

$1 \leq j \leq m$

Сашо Николов

@SashoNikolov: да, я имею в виду, что для каждой пары (и в доказательстве ) точно один включен в ; Я отредактирую ответ

(x_{2 i - 1}, x_{2 i})

$(x_{2i-1},x_{2i})$

(x_{2 i - 1}^{'}, x_{2 i}^{'})

$(x'_{2i-1}, x'_{2i})$

X_{1}

$X_1$

Марцио Де Биаси

РЕДАКТИРОВАТЬ: в моем оригинальном доказательстве была ошибка. Теперь я считаю, что это исправлено.

Мы сводим к этой проблеме проблему РАВНЫХ СУММ. Равноправные подмножества сумм - это проблема: при заданном наборе целых чисел найти два непересекающихся подмножества, которые имеют одинаковую сумму. РАВНЫЕ СУБСЕТЫ, как известно, являются NP-полными. $m$

Предположим, что эти битовые строки были не векторами, а представлениями битных чисел в двоичном виде. Тогда задача будет NP-полной за счет сокращения от EQUAL SUM SUBSETS. Я покажу, как заставить эти векторы вести себя как двоичные числа. Нам нужно уметь делать переноски; то есть для каждой пары смежных координат мы должны иметь возможность заменить вектор ..02 .. на ..10 ... $n$

Как мы можем сделать это? Нам нужен гаджет, который позволяет нам это делать. В частности, нам нужны два подмножества, чьи суммы равны ..02 .. x и ..10 .. x, где x - битовая строка с использованием новых координат (т. Е. Координат, которые не являются ни одной из координат, составляющих двоичный файл представления), и где есть только один способ создать два подмножества с одинаковой суммой в новых битовых позициях, соответствующих х. $n$

Это довольно легко сделать. Для каждой пары соседних позиций битов добавьте три вектора следующей формы. Здесь последние два бита являются координатами, которые ненулевые только в этих трех векторах, и каждый бит, явно не указанный ниже, равен 0.

..10 .. 11
..01 .. 10
..01 .. 01

Позвольте мне сделать пример. Мы хотим показать, как работает 5 + 3 = 8.

Вот 8 = 5 + 3 в двоичном виде:

1000

знак равно

0101
0011

Эти битовые строки дают одинаковую сумму в двоичном виде, но не в векторном сложении.

Теперь у нас есть переносы в 1, 2, 4 местах, поэтому нам нужно добавить три уравнения из трех векторов в уравнение, чтобы выполнить эти переносы.

1000 00 00 00
0001 00 00 01
0001 00 00 10
0010 00 01 00
0010 00 10 00
0100 01 00 00
0100 10 00 00

знак равно

0101 00 00 00
0011 00 00 00
0010 00 00 11
0100 00 11 00
1000 11 00 00

Эти наборы теперь имеют одинаковую сумму в сложении векторов. Суммы:

1222 11 11 11

в обоих случаях.

Эта конструкция прекрасно работает, если на одну позицию приходится только один перенос, но потенциально может быть до переносов на позицию, и вам необходимо убедиться, что ваша конструкция может обрабатывать до переносов, и что разные переносы не мешают друг с другом. Например, если вы добавили два разных набора из трех векторов для одной и той же пары смежных позиций (что я и предложил в моем первоначальном доказательстве): $n$ $n$

..01 .. 01 00
..01 .. 10 00
..10 .. 11 00
..01 .. 00 01
..01 .. 00 10
..10 ... 00 11

у вас проблема в том, что вы получаете два разных набора векторов, дающих одинаковую сумму:

..01 .. 01 00
..01 .. 10 00
..10 .. 00 11

знак равно

..01 .. 00 01
..01 .. 00 10
.. 10 .. 11 00

Как это исправить? Добавьте один набор векторов, который позволяет переносить 1, один набор, который позволяет переносить 2, и один набор для 4, 8, , 2 . Я не собираюсь сейчас разбирать детали этой конструкции, но она должна быть достаточно простой. Поскольку каждое число имеет уникальное двоичное представление, это позволит вам переносить любое число до . Например, для переноса 4 вам нужно найти четыре вектора, которые имеют одинаковую сумму с двумя векторами, и для которых это единственное линейное соотношение между двумя наборами. Например, набор $\ldots$ $^{\lfloor \log n \rfloor}$ $n$

..01 .. 11000
..01 .. 00100
..01 .. 00010
..01 .. 00001
..10 .. 10001
..10 .. 01110

работает. Вы можете легко проверить, что отношение

11000
00100
00010
00001

знак равно

10001
01110

является единственным возможным отношением между этими шестью векторами, потому что матрица, образованная этими шестью строками, имеет ранг 5.

Питер Шор
источник

В разъяснении вы говорите: «Теперь у нас есть поводы в 1, 2, 4 местах»; но в задаче мы не знаем, какие векторы выбраны, поэтому мы должны добавить гаджет переноса в каждую соседнюю позицию бита? И в первом списке примера есть 7 векторов, это правильно?

Марцио Де Биаси

Предположим, есть решение для задачи с суммой подмножеств. То есть: у нас 3 + 5 = 8. Теперь мы можем посмотреть на дополнение в этом свидетеле и выяснить, где находятся переносчики. Это дает нам решение проблемы сложения векторов. У одной проблемы есть решение тогда и только тогда, когда у другой.

Питер Шор

Но как работает сокращение, например, если экземпляр суммы поднабора равен и целевой суммы (каков соответствующий экземпляр вектора)?

2, 3, 5, 7

$2,3,5,7$

8

$8$

Марцио Де Биаси

PS Я также нашел доказательство того, что проблема является NP-полной, но она намного длиннее вашей, поэтому я пытаюсь ее понять ... проще - лучше :-)

Марцио Де Биаси

Это означает, что для второй проблемы мы должны добавить гаджет переноса в каждую соседнюю позицию бита. Фактически, поскольку у нас может быть переносов в этой позиции, мы должны добавить копий гаджета переноса в эту позицию бита. И я только что понял, что это не работает - мы должны быть умнее. Я знаю, как это сделать, но мне придется пересмотреть ответ.

n - 1

$n-1$

n - 1

$n-1$

Питер Шор

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

Переформулировка проблемы, как указано в моем комментарии к вопросу:

Вход: векторов более , является частью ввода $n$ $X = \{ x_1, \dots, x_n \}$ $\{0,1\}^m$ $m$

Вопрос: Существуют ли два разных подмножества таких что $A,B \subseteq X$

\sum_{x \in A} x = \sum_{x \in B} x

$\sum_{x \in A} x = \sum_{x \in B} x$

Может быть, я должен отметить, что нужно рассматривать как мультимножества (векторы не должны быть уникальными), а суммы превышают . $X,A,B$ $\mathbb{N}$

Я предлагаю называть эту проблему 2SUBSET-BINARY-VECTOR-SUM из-за того, что мы ищем 2 подмножества бинарных векторов.

Некоторые наблюдения:

Если содержит один вектор несколько раз, ответ становится тривиальным. Пусть и . Тогда работает как свидетель. $X$ $x_i,x_j \in X$ $x_i = x_j$ $A = \{x_i\}, B = \{x_j\}$
Если один из векторов в содержит только 0, он тривиален. Пусть будет этим вектором. Тогда для каждого следует свидетель. $X$ $0 \in X$ $A \subseteq X \setminus \{ 0 \}$ $B = A \cup \{ 0 \}$
Предположим , что существует свидетель такое , что . Это означает, что каждый вектор, который находится в но не в должен состоять только из нулей. $A \subset B$ $B$ $A$
Для перечисления вышеупомянутых двух пунктов: свидетель с существует тогда и только тогда, когда хотя бы один из векторов в содержит только нули $A,B$ $A \subset B$ $X$
Предположим, существует такой свидетель , что . Вы можете удалить общие элементы в обоих наборах и при этом иметь правильного свидетеля. $A,B$ $A \cap B \neq \emptyset$

Эти точки означают, что вы ищете разбиение на два набора ( ) или три набора. Третий набор представляет векторы , которые не были выбраны для любого или . Пусть - числа Стирлинга второго рода - количество способов разбить набор из объектов на непустых разбиений. Тогда есть возможных решений, поэтому грубая сила здесь неосуществима. $X$ $A \cup B = X$ $A$ $B$ $S(n,k)$ $n$ $k$ $S(n,3)+S(n,2)$

Если вы позволите векторам превышать (2SUBSET-VECTOR-SUM), то мы можем попытаться свести UNIQUE-PARTITION к этой проблеме. Пусть и просто пропустите экземпляр UNIQUE-PARTITION (если он содержит 0, сначала удалите его, чтобы избежать тривиальных решений). Однако это не работает, поскольку возможные решения не обязательно содержат все входные элементы: $\mathbb{N}^m$ $m=1$ $A,B$

Рассмотрим . Это не в UNIQUE-PARTITION, но в 2SUBSET-VECTOR-SUM. Возможно, используя мы можем использовать дополнительные векторные записи, чтобы заставить разделить ввод. $\{1,2,3,5\}$ $A=\{1,2\} , B = \{3\}$ $m>1$ $A,B$

Джон Д.
источник

Решите, содержит ли ядро ​​матрицы ненулевой вектор, все записи которого равны -1, 0 или 1

Ответы:

Решите, содержит ли ядро матрицы ненулевой вектор, все записи которого равны -1, 0 или 1