Putuskan apakah kernel matriks berisi semua vektor yang bukan nol semua entrinya adalah -1, 0, atau 1

Diberi oleh matriks biner (entri adalah atau ), masalahnya adalah menentukan apakah ada dua vektor biner sehingga (semua operasi dilakukan dengan ). Apakah ini masalah NP-hard?n M 0 1 v 1 ≠ v 2 M v 1 = M v 2 $m$$n$$M$$0$$1$$v_1 \ne v_2$$Mv_1 = Mv_2$$\mathbb{Z}$

Jelas dalam NP karena Anda dapat memberikan dua vektor sebagai saksi.

---

Ekuivalen: Mengingat , apakah ada non-nol vektor v ∈ { - 1 , 0 , 1 } n sehingga M v = 0 ?$M$$v\in \{-1,0,1\}^n$$Mv=0$

Setara: Diberikan $n$ vektor $X=\{x_1,\dots,x_n\}$ lebih dari $\{0,1\}^m$ , adakah dua himpunan bagian yang berbeda $A,B \subseteq X$ sedemikian rupa sehingga ?$\sum_{x \in A} x = \sum_{x \in B} x$

Saya menggunakan formulasi yang setara dengan user17410:

Input: $n$ vektor $X = \{ x_1, \dots, x_m \}$ lebih dari $\{0,1\}^n$ , $n$ adalah bagian dari input
Pertanyaan: Apakah ada dua himpunan bagian berbeda , B ⊆ $A,B \subseteq X$ sedemikian rupa sehingga

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

Bukti kekerasan melibatkan banyak reduksi tingkat menengah yang mengikuti "rantai" yang sama yang digunakan untuk membuktikan kekerasan dari masalah SUMU SUBSET EQUAL standar:

X3C $\leq$ SUBSET SUM $\leq$ PARTITION $\leq$ BAHKAN-ODD PARTITION $\leq$ EQUAL SUBSET SUM

(Saya masih memeriksanya jadi mungkin salah :)

LANGKAH 1

Masalah berikut ( 0-1 SUMBER VEKTOR SUMBER ) adalah NP-complete: diberikan , x i vektor lebih dari { 0 , 1 } n dan jumlah vektor target t , putuskan apakah ada A ⊆ X sedemikian rupa sehingga ∑ x ∈ A x = t Bukti : Pengurangan langsung dari SAMBUTAN SAMPAI DENGAN 3-SETS (X3C): diberikan seperangkat elemen n Y = { $X = \{ x_1, \dots, x_m \}$$x_i$$\{0,1\}^n$$t$$A \subseteq X$

$$\sum_{x \in A} x = t$$ $n$ dan koleksi C dari m tiga unsur himpunan C = { C 1 , . . . , C m } kita build 0-1 VECTOR SUM misalnya pengaturan yang sesuai x i [ j ] = 1 jika dan hanya jika elemen j termasuk dalam C i ; t = [ 1 , 1 , . . ] .$Y = \{y_1,...,y_n\}$$C$$m$$C = \{C_1,...,C_m\}$$x_i[j] = 1$$j$$C_i$$t = [1,1,...1]$

LANGKAH 2 Menemukan dua himpunan bagian jumlah yang sama antara m 0-1 vektor di atas { 0 , 1 } n , sama dengan menemukan dua himpunan bagian jumlah yang sama A , B dari vektor dengan elemen ukuran terikat x 1 . . . x m di mana m a x { x i } = O ( ( m n ) k ) untuk k tetap .$A,B$$m$$\{0,1\}^n$$A,B$$x_1 ... x_m$$max\{x_i\} = O((mn)^k)$$k$

Misalnya kumpulan vektor:

x1 2 1 0 1
x2 1 2 3 1

Sama dengan vektor 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

Secara informal, vektor 0-1 dikelompokkan (jika Anda memilih satu vektor dari grup x2 dan menambahkannya ke subset , maka Anda dipaksa untuk memasukkan dalam A dua lainnya dan meletakkan yang terakhir di subset B ) dan jumlahnya dilakukan dalam unary (ini adalah alasan mengapa yang sesuai vektor non biner harus mengandung unsur-unsur yang polynomially dibatasi sehubungan dengan m n ).$A$$A$$B$$mn$

Jadi masalah berikut ini adalah NP-complete.

LANGKAH 3

Masalah berikut ( 0-1 PARTEKSI VEKTOR ) adalah NP-lengkap: diberikan , x i vektor lebih dari { 0 , 1 } n memutuskan apakah X dapat dipartisi dalam dua himpunan bagian B 1 , B 2 sedemikian rupa sehingga ∑ x ∈ B 1 x = ∑ x ∈ B 2$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$$

Bukti : Pengurangan dari 0-1 SUMBER VEKTOR: diberikan dan vektor jumlah target t ; misalkan S = ∑ x i , kita tambahkan ke X vektor-vektor berikut: b ′ = - t + 2 S dan b ″ = t + $X = \{ x_1, \dots, x_m \}$$t$$S = \sum x_i$$X$$b' = -t + 2S$$b'' = t + S\;$: $B = X \cup \{b',b''\}$ .

( ) Misalkan terdapat A ⊆ X sehingga Σ x ∈ A x = t ; kita menetapkan B 1 = A ∪ { b ′ } dan B 2 = B ∖ B 1 = X ∖ { A } ∪ { b ″ } ; kita memiliki ∑ x ∈ B 1 = b ′ + ∑ x ∈ $\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''\}$∑ x ∈ B 2 = b ″ + ∑ x ∈ X ∖ A x = b ″ + S - ∑ x ∈ A x = 2

$$\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\setminus A} x = b'' + S - \sum_{x \in A} x=2S$$

( ) Misalkan B 1 dan B 2 memiliki jumlah yang sama. b ′ , b ″ tidak bisa keduanya memiliki himpunan yang sama (jika jumlah mereka ≥ 3 S dan tidak dapat "seimbang" dengan unsur-unsur di himpunan lainnya). Misalkan b ′ = - t + 2 S ∈ B 1 ; kita punya:$\Leftarrow$$B_1$$B_2$$b', b''$$\geq 3S$$b' = -t + 2S \in B_1$

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

Karenanya kita harus memiliki dan B 1 ∖ { b ′$\sum_{x \in B_1 \setminus\{b'\}} x = t$$B_1 \setminus\{b'\}$ adalah solusi yang valid untuk 0-1 VEKTOR SUM.

Kami hanya mengizinkan 0-1 vektor di set , jadi vektor b ′ , b ″ harus "diwakili secara unary" seperti yang ditunjukkan pada LANGKAH 2.$B$$b', b''$

LANGKAH 3

Masalahnya adalah masih NP-lengkap jika vektor diberi nomor dari dan dua himpunan bagian X 1 , X 2 harus memiliki ukuran yang sama dan kami mensyaratkan bahwa X 1 mengandung tepat satu dari x 2 i - 1 , x 2 i untuk 1 ≤ i ≤ n (jadi, dengan batasan ukuran yang sama , elemen lain dari pasangan harus dimasukkan dalam X 2 ) ( 0-1 VECTOR EVEN-ODD PARTITION ).$x_1,...,x_2n$$X_1,X_2$$X_1$$x_{2i-1},x_{2i}$$1 \leq i \leq n$$X_2$

Bukti:: Pengurangannya dari 0-1 PARTISI VEKTOR dan mirip dengan pengurangan dari PARTISI menjadi PARTISIPAN GENAP. Jika adalah vektor m di atas { 0 , 1 } n ganti setiap vektor dengan dua vektor di atas { 0 , 1 } 2 n + 2 m :$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 

Karena elemen , vektor x ′ 2 i - 1 dan x ′ 2 i tidak dapat dimuat dalam subset yang sama; dan solusi yang valid untuk PARTISI 0-1 VEKTOR EVEN-ODD sesuai dengan solusi yang valid dari PARTISI 0-1 VEKTOR asli (cukup pilih elemen 2m + 1..2m + n dari masing-masing vektor larutan yang membuang vektor yang berisi semua nol di posisi itu).$2i$$x'_{2i-1}$$x'_{2i}$

LANGKAH 4

0-1 SUMBER SUMBER BAGIAN VEKTOR (masalah dalam pertanyaan) adalah NP-complete: pengurangan dari 0-1 VECTOR EVEN-ODD PARTITION mirip dengan pengurangan dari SUMBER SUMBER ODD menjadi SUMBER SUMBER SUMBER, seperti yang dibuktikan dalam Gerhard J. Woeginger , Zhongliang Yu, Di sama-bagian-sum masalah : diberi memerintahkan set dari 2 m vektor di atas { 0 , 1 } n , kami membangun satu set Y dari 3 m vektor di atas { 0 $A = \{x_1,...,x_{2m}\}$$2m$$\{0,1\}^n$$Y$$3m$$\{0,1\}^{2m+n}$.

For every vector $x_{2i-1}, 1 \leq i \leq m$ we build a vector $y_{2i-1}$ over $\{0,1\}^{2m+n}$ in this way:

  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

$> 1$

$Y$$Y_1,Y_2$ subsets having equal sum if and only if $X$ has an even-odd partition.

EDIT: My original proof had a bug. I now believe that it is fixed.

We reduce the problem of EQUAL SUM SUBSETS to this problem. EQUAL SUM SUBSETS is the problem of: given a set of $m$ integers, find two disjoint subsets which have the same sum. EQUAL SUM SUBSETS is known to be NP-complete.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from EQUAL SUM SUBSETS. I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

How can we do that? We need a gadget that lets us do that. In particular, we need two subsets whose sums are ..02.. x and ..10.. x, where x is a bit string using new coordinates (i.e., coordinates which aren't any of the $n$ coordinates making up the binary representations), and where there is only one way to create two subsets with the same sum in the new bit positions corresponding to x.

This is fairly easy to do. For every pair of adjacent bit positions, add three vectors of the following form. Here the last two bits are coordinates which are non-zero only in these three vectors, and every bit not explicitly given below is 0.

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

Let me do an example. We want to show how 5+3=8 works.

Here is 8 = 5 + 3 in binary:

1000

=

0101
0011

These bit strings give the same sum in binary, but not in vector addition.

Now, we have carries in the 1, 2, 4 places, so we need to add three sets of three vectors to the equation so as to perform these carries.

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

These sets now have the same sum in vector addition. The sums are:

1222 11 11 11

in both cases.

This construction works great if there is only one carry per position, but there could potentially be up to $n$ carries per position, and you need to make sure that your construction can handle up to $n$ carries, and that the different carries don't interfere with each other. For instance, if you added two different sets of three vectors for the same pair of adjacent positions (which is what I proposed in my original proof):

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

you have the problem that you get two different sets of vectors giving the same sum:

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

=

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

How to fix this? Add one set of vectors which lets you carry 1, one set which lets you carry 2, and one set for 4, 8, $\ldots$, 2$^{\lfloor \log n \rfloor}$. I'm not going to go work out the details of this construction right now, but it should be fairly straightforward. Since each number has a unique binary representation, this will let you carry any number up to $n$. For carrying 4, for example, you need find four vectors which have the same sum as two vectors, and for which this is the only linear relation between the two sets. For example, the set

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

bekerja. Anda dapat dengan mudah memeriksa hubungannya

11000
00100
00010
00001

=

10001
01110

adalah satu-satunya hubungan yang mungkin di antara enam vektor ini karena matriks yang dibentuk oleh enam baris ini memiliki peringkat 5.

Ini tidak menjawab pertanyaan tetapi mungkin berisi beberapa pengamatan bermanfaat. Saya tidak ingin meletakkannya sebagai komentar karena saya menemukan komentar yang panjang dan terfragmentasi mengganggu untuk dibaca

Rumusan masalah seperti yang dinyatakan dalam komentar saya untuk pertanyaan:

Memasukkan: $n$ vektor $X = \{ x_1, \dots, x_n \}$ lebih $\{0,1\}^m$, $m$ adalah bagian dari input

Pertanyaan: Apakah ada dua himpunan bagian yang berbeda $A,B \subseteq X$ seperti yang

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

Mungkin saya harus perhatikan bahwa orang harus menghargai $X,A,B$ sebagai multiset (vektor tidak boleh unik) dan jumlahnya sudah berakhir $\mathbb{N}$.

Saya mengusulkan untuk menyebut masalah ini 2SUBSET-BINARY-VECTOR-SUM karena kami mencari 2 subset vektor biner.

Beberapa pengamatan:

• Jika $X$berisi satu vektor beberapa kali, jawabannya menjadi sepele. Membiarkan$x_i,x_j \in X$ dan $x_i = x_j$. Kemudian$A = \{x_i\}, B = \{x_j\}$ bekerja sebagai saksi.

• Jika salah satu vektor di $X$hanya mengandung 0 itu sepele. Membiarkan$0 \in X$menjadi vektor itu. Lalu untuk setiap$A \subseteq X \setminus \{ 0 \}$ itu mengikuti $B = A \cup \{ 0 \}$ adalah saksi.

• Anggap ada saksi sedemikian rupa $A \subset B$. Ini menyiratkan bahwa setiap vektor yang ada di$B$ tapi tidak di $A$ harus terdiri dari nol saja.

• Untuk merangkum dua poin di atas: seorang saksi $A,B$ dengan $A \subset B$ ada jika setidaknya satu vektor di $X$ hanya mengandung nol

• Anggap ada saksi $A,B$ seperti yang $A \cap B \neq \emptyset$. Anda dapat menghapus elemen umum di kedua set dan masih memiliki saksi yang benar.

Poin-poin ini pada dasarnya berarti bahwa Anda mencari partisi $X$ menjadi dua set ($A \cup B = X$) atau tiga set. Set ketiga mewakili vektor yang tidak dipilih untuk keduanya$A$ atau $B$. Membiarkan$S(n,k)$ menjadi nomor Stirling dari jenis kedua - jumlah cara untuk mempartisi sekumpulan $n$ objek menjadi $k$partisi tidak kosong. Lalu ada$S(n,3)+S(n,2)$ solusi yang mungkin, jadi brute force tidak layak di sini.

Jika Anda membiarkan vektor berakhir $\mathbb{N}^m$(2SUBSET-VECTOR-SUM), maka kita dapat mencoba untuk mengurangi UNIK-PARTISI untuk masalah ini. Membiarkan$m=1$dan cukup berikan instance UNIQUE-PARTITION (jika berisi 0, hapus dulu untuk menghindari solusi sepele). Namun, ini tidak berhasil karena kemungkinan solusi$A,B$ tidak harus mengandung semua elemen input:

Mempertimbangkan $\{1,2,3,5\}$. Ini bukan di PARTAI UNIK tetapi$A=\{1,2\} , B = \{3\}$dalam 2SUBSET-VECTOR-SUM. Mungkin menggunakan$m>1$ kita dapat menggunakan entri vektor tambahan untuk memaksa $A,B$ untuk mempartisi input.