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

27

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 1v 2 M v 1 = M v 2 ZmnM01v1v2Mv1=Mv2Z

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 ?Mv{1,0,1}nMv=0

Setara: Diberikan n vektor X={x1,,xn} lebih dari {0,1}m , adakah dua himpunan bagian yang berbeda A,BX sedemikian rupa sehingga ?xAx=xBx

Mohammad Al-Turkistany
sumber
Kecuali aku salah paham pertanyaan, apakah ini tidak setara dengan menentukan jika ada non-nol v sehingga Mv=0 ? Dan bukankah ini diselesaikan dengan menentukan peringkat M. ?
mhum
8
@mhum tidak, itu setara dengan menentukan jika ada nol v{1,0,1}n sehingga Mv=0 .
Sasho Nikolov
Ah. Aku merindukan itu vsaya juga harus biner. Kesalahanku.
mhum
2
Sepertinya masalah kelayakan untuk 0/1-Integer Programming. Apakah operasi lebih dari Z atau lebih dari Z2 ?
Kaveh
3
Reformulasi masalah: Diberikan n vektor X={x1,,xn} lebih dari {0,1}m . Apakah ada dua himpunan bagian yang berbeda A,BX sehingga xAx=xBx ? Saya akan berpikir bahwa itu lebih cenderung NP-keras jika jumlahnya tidak diambil modulo dua, yaitu operasi lebih dari Z
John D.

Jawaban:

7

Saya menggunakan formulasi yang setara dengan user17410:

Input: n vektor X={x1,,xm} lebih dari {0,1}n , n adalah bagian dari input
Pertanyaan: Apakah ada dua himpunan bagian berbeda , B XA,BX sedemikian rupa sehingga

xAx=xBx

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

X3C SUBSET SUM PARTITION BAHKAN-ODD PARTITION 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 = { yX={x1,,xm}xi{0,1}ntAX

xAx=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={y1,...,yn}CmC={C1,...,Cm}xsaya[j]=1jCsayat=[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 .SEBUAH,Bm{0,1}nSEBUAH,Bx1...xmmax{xi}=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 ).AABmn

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 xB={x1,,xm}xi{0,1}nXB1,B2

xB1x=xB2x

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 + SX={x1,,xm}tS=xiXb=t+2Sb=t+S: B=X{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 AAXxAx=tB1=A{b}B2=BB1=X{A}{b}x B 2 = b + x X A x = b + S - x A x = 2 S

xB1=b+xAx=tt+S=2S
xB2=b+xXAx=b+SxAx=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:B1B2b,b3Sb=t+2SB1

t+2S+xB1{b}x=t+S+xB2{b}x

Karenanya kita harus memiliki dan B 1{ b }xB1{b}x=tB1{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.Bb,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 ).x1,...,x2nX1,X2X1x2i1,x2i1inX2

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={x1,...,xm}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).2ix2i1x2i

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={x1,...,x2m}2m{0,1}nY3m{0,1}2m+n.

For every vector x2i1,1im we build a vector y2i1 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}

x2i,1im1y2i{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}

x2m

  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

YY1,Y2 subsets having equal sum if and only if X has an even-odd partition.

Marzio De Biasi
sumber
what you call 0-1 vector partition is equivalent to the problem of determining if a set system has discrepancy 0. this is NP hard, since it captures e.g. the 2-2-set-splitting problem, see thm 9 in this paper by guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps; my paper has a bit more on the hardness of discrepancy paul.rutgers.edu/~anikolov/Files/charikarM.pdf
Sasho Nikolov
also I believe you mis-state the even-odd partition problem. if no two consecutive vectors can be in the same set the problem is trivial. i believe you mean that |Xi{x2j1,x2j}|=1 is required for all i{1,2} and 1jm
Sasho Nikolov
@SashoNikolov: yes, I mean that for every pair (x2i1,x2i) (and in the proof (x2i1,x2i)) exactly one is included in X1; I'll edit the answer
Marzio De Biasi
8

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, , 2logn. 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.

Peter Shor
sumber
Klarifikasi, Anda mengatakan "Sekarang, kami memiliki membawa di 1, 2, 4 tempat"; tetapi dalam masalah kita tidak tahu vektor mana yang dipilih sehingga kita harus menambahkan carry gadget ke setiap posisi bit yang berdekatan? Dan dalam daftar contoh pertama ada 7 vektor, apakah benar?
Marzio De Biasi
Misalkan punya solusi untuk masalah jumlah subset. Yaitu: kita memiliki 3 + 5 = 8. Sekarang, kita bisa melihat penambahan dalam saksi ini dan mencari tahu di mana membawa. Ini memberi kita solusi untuk masalah penambahan vektor. Satu masalah memiliki solusi jika dan hanya jika yang lain memiliki.
Peter Shor
Tetapi bagaimana reduksi bekerja misalnya jika turunan dari jumlah bagian adalah 2,3,5,7 dan jumlah target 8 (apa contoh vektor yang sesuai)?
Marzio De Biasi
PS Saya juga menemukan bukti bahwa masalahnya adalah NP-lengkap, tetapi jauh lebih lama dari Anda, jadi saya mencoba memahaminya ... lebih sederhana lebih baik :-)
Marzio De Biasi
Ini berarti bahwa untuk masalah kedua, kita harus menambahkan gadget carry ke setiap posisi bit yang berdekatan. Sebenarnya, karena kita mungkin punyan-1 Membawa dalam posisi itu, kita harus menambahkan n-1salinan membawa gadget ke posisi bit itu. Dan saya baru sadar itu tidak berhasil - kita harus lebih pintar. Saya tahu bagaimana melakukannya, tetapi saya harus merevisi jawabannya.
Peter Shor
3

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={x1,...,xn} lebih {0,1}m, m adalah bagian dari input

Pertanyaan: Apakah ada dua himpunan bagian yang berbeda SEBUAH,BX seperti yang

xSEBUAHx=xBx

Mungkin saya harus perhatikan bahwa orang harus menghargai X,SEBUAH,B sebagai multiset (vektor tidak boleh unik) dan jumlahnya sudah berakhir N.

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

Beberapa pengamatan:

  • Jika Xberisi satu vektor beberapa kali, jawabannya menjadi sepele. Membiarkanxsaya,xjX dan xsaya=xj. KemudianSEBUAH={xsaya},B={xj} bekerja sebagai saksi.

  • Jika salah satu vektor di Xhanya mengandung 0 itu sepele. Membiarkan0Xmenjadi vektor itu. Lalu untuk setiapSEBUAHX{0} itu mengikuti B=SEBUAH{0} adalah saksi.

  • Anggap ada saksi sedemikian rupa SEBUAHB. Ini menyiratkan bahwa setiap vektor yang ada diB tapi tidak di SEBUAH harus terdiri dari nol saja.

  • Untuk merangkum dua poin di atas: seorang saksi SEBUAH,B dengan SEBUAHB ada jika setidaknya satu vektor di X hanya mengandung nol

  • Anggap ada saksi SEBUAH,B seperti yang SEBUAHB. 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 (SEBUAHB=X) atau tiga set. Set ketiga mewakili vektor yang tidak dipilih untuk keduanyaSEBUAH atau B. MembiarkanS(n,k) menjadi nomor Stirling dari jenis kedua - jumlah cara untuk mempartisi sekumpulan n objek menjadi kpartisi tidak kosong. Lalu adaS(n,3)+S(n,2) solusi yang mungkin, jadi brute force tidak layak di sini.

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

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

John D.
sumber