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 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 ?
Setara: Diberikan vektor lebih dari , adakah dua himpunan bagian yang berbeda sedemikian rupa sehingga ?
cc.complexity-theory
np-hardness
linear-algebra
Mohammad Al-Turkistany
sumber
sumber
Jawaban:
Saya menggunakan formulasi yang setara dengan user17410:
Input:n vektor X={x1,…,xm} lebih dari {0,1}n , n adalah bagian dari input A,B⊆X sedemikian rupa sehingga
Pertanyaan: Apakah ada dua himpunan bagian berbeda , 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≤ 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}n t A ⊆ X
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 x1...xm max{xi}=O((mn)k) k
Misalnya kumpulan vektor:
Sama dengan vektor 0-1:
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 xB={x1,…,xm} xi {0,1}n X B1,B2
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} t S=∑xi X b′=−t+2S b′′=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 ∈ A⇒ A⊆X ∑x∈Ax=t B1=A∪{b′} B2=B∖B1=X∖{A}∪{b′′} ∑ x ∈ B 2 = b ″ + ∑ x ∈ X ∖ A x = b ″ + S - ∑ x ∈ A x = 2 S
( ) 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:⇐ B1 B2 b′,b′′ ≥3S b′=−t+2S∈B1
Karenanya kita harus memiliki dan B 1 ∖ { b ′ }∑x∈B1∖{b′}x=t B1∖{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 ).x1,...,x2n X1,X2 X1 x2i−1,x2i 1≤i≤n X2
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
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={x1,...,x2m} 2m {0,1}n Y 3m {0,1}2m+n .
For every vectorx2i−1,1≤i≤m we build a vector y2i−1 over {0,1}2m+n in this way:
sumber
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 ofm 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 ofn -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 then 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.
Let me do an example. We want to show how 5+3=8 works.
Here is 8 = 5 + 3 in binary:
=
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.
=
These sets now have the same sum in vector addition. The sums are:
in both cases.
This construction works great if there is only one carry per position, but there could potentially be up ton 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):
you have the problem that you get two different sets of vectors giving the same sum:
=
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,… , 2⌊logn⌋ . 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
bekerja. Anda dapat dengan mudah memeriksa hubungannya
=
adalah satu-satunya hubungan yang mungkin di antara enam vektor ini karena matriks yang dibentuk oleh enam baris ini memiliki peringkat 5.
sumber
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 berbedaA , B ⊆ X seperti yang
Mungkin saya harus perhatikan bahwa orang harus menghargaiX, A , 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:
JikaX berisi satu vektor beberapa kali, jawabannya menjadi sepele. Membiarkanxsaya, xj∈ X dan xsaya= xj . KemudianA = { xsaya} , B = { xj} bekerja sebagai saksi.
Jika salah satu vektor diX hanya mengandung 0 itu sepele. Membiarkan0 ∈ X menjadi vektor itu. Lalu untuk setiapA ⊆ X∖ { 0 } itu mengikuti B = A ∪ { 0 } adalah saksi.
Anggap ada saksi sedemikian rupaA ⊂ B . Ini menyiratkan bahwa setiap vektor yang ada diB tapi tidak di SEBUAH harus terdiri dari nol saja.
Untuk merangkum dua poin di atas: seorang saksiA , B dengan A ⊂ B ada jika setidaknya satu vektor di X hanya mengandung nol
Anggap ada saksiA , B seperti yang A ∩ B ≠ ∅ . Anda dapat menghapus elemen umum di kedua set dan masih memiliki saksi yang benar.
Poin-poin ini pada dasarnya berarti bahwa Anda mencari partisiX menjadi dua set (A ∪ B = 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 k partisi tidak kosong. Lalu adaS( n , 3 ) + S( n , 2 ) solusi yang mungkin, jadi brute force tidak layak di sini.
Jika Anda membiarkan vektor berakhirNm (2SUBSET-VECTOR-SUM), maka kita dapat mencoba untuk mengurangi UNIK-PARTISI untuk masalah ini. Membiarkanm = 1 dan cukup berikan instance UNIQUE-PARTITION (jika berisi 0, hapus dulu untuk menghindari solusi sepele). Namun, ini tidak berhasil karena kemungkinan solusiA , B tidak harus mengandung semua elemen input:
Mempertimbangkan{ 1 , 2 , 3 , 5 } . Ini bukan di PARTAI UNIK tetapiA = { 1 , 2 } , B = { 3 } dalam 2SUBSET-VECTOR-SUM. Mungkin menggunakanm > 1 kita dapat menggunakan entri vektor tambahan untuk memaksa A , B untuk mempartisi input.
sumber