Apakah ada algoritma waktu polinomial untuk menentukan apakah rentang satu set matriks berisi matriks permutasi?

Saya ingin mencari algoritma waktu polinomial yang menentukan apakah rentang set matriks yang diberikan berisi matriks permutasi.

Jika ada yang tahu jika masalah ini dari kelas kompleksitas yang berbeda, itu akan sangat membantu.

EDIT: Saya telah menandai pertanyaan ini dengan Linear Programming, karena saya memiliki kecurigaan yang kuat bahwa jika solusi seperti itu ada, itu akan menjadi semacam algoritma pemrograman linier. Alasan saya percaya ini adalah karena titik-titik ekstrim dari polytope Birkhoff adalah matriks permutasi. Jika Anda kemudian dapat menemukan fungsi objektif yang dimaksimalkan atau diminimalisasi hanya pada simpul-simpul dari Birkhoff polytope, Anda dapat membatasi fungsi Anda ke persimpangan polytope dan subruang vektor Anda, kemudian memaksimalkannya dalam waktu polinomial. Jika nilai ini adalah matriks permutasi, Anda akan tahu set berisi permutasi. Itulah pemikiran saya tentang masalah ini.

EDIT 2: Setelah beberapa pemikiran lagi, tampak bagi saya bahwa matriks permutasi adalah unsur-unsur dari Birkhoff Polytope dengan norma Euclidean $\sqrt{n}$ , kita mempertimbangkan polytope Birkhoff menjadi convex hull dari $n \times n$ matriks permutasi. Mungkin itu juga penting.

EDIT 3: Saya menambahkan tag pemrograman semidefinite, karena setelah komentar saya sebelumnya, saya mulai berpikir bahwa solusi pemrograman semidefinite mungkin dilakukan karena sekarang algoritma optimasi kuadratik dibatasi linear.

cc.complexity-theory linear-algebra linear-programming semidefinite-programming polynomial-time Nick
sumber

Apa jenis entri yang akan dimiliki matriks input?

$\;$

Entri bisa di bidang apa pun, ada beberapa kebebasan dalam cara mengatur matriks; namun, Anda menginginkan bidang yang cukup besar (jadi bidang karakteristik 2 tidak akan bagus misalnya).

Nick

Bisakah menjelaskan berapa rentang dari satu set matriks?

Mohammad Al-Turkistany

Mohammad: Saya pikir ini adalah kombinasi linear dari serangkaian matriks.

Vivek Bagaria

@ DavidvidRicherby Saya pikir kebingungan Mohammad berasal dari fakta bahwa biasanya kita menganggap matriks mewakili peta linier, dan rentang peta linear kadang-kadang digunakan sebagai istilah lain untuk jangkauannya. Tapi itu tidak masuk akal di sini, jadi saya kira kita berpikir matriks sebagai elemen ruang vektor

Sasho Nikolov

Jawaban:

Dalil. Masalah dalam posting adalah NP-hard, dengan reduksi dari Subset-Sum.

Tentu saja karena masalahnya tidak mungkin memiliki algoritma poli-waktu seperti yang diminta oleh op.

Inilah intuisinya. Masalah dalam pos adalah

Apakah ada matriks permutasi dalam rentang satu set matriks?

Ini pada dasarnya sama dengan

Apakah ada matriks permutasi yang (menganggap matriks sebagai vektor) memenuhi beberapa batasan linear yang diberikan?

Ini pada gilirannya sama dengan

Apakah ada pencocokan sempurna (dalam grafik bipartit lengkap) yang vektor kejadiannya memenuhi beberapa batasan linear yang diberikan?

Mengurangi Subset-Jumlah ke masalah terakhir adalah latihan standar.

Ini bukti terperinci.

Definisikan masalah antara berikut:

Matching-Sum:

$G=(U,V,E)$ $T$

$G$ $T$

Lemma 1 . Subset-Sum poly-time dikurangi menjadi Matching-Sum.

Membuktikan ini adalah latihan pekerjaan rumah standar. Buktinya ada di akhir.

Lemma 2. Matching-Sum poly-time berkurang menjadi masalah pada postingan.

$G=(U,V,E)$ $w:U\times V\rightarrow \mathbb{N}_+$ $T\in \mathbb{N}_+$ $U=\{u_1,\ldots,u_n\}$ $V=\{v_1, \ldots, v_n\}$ $i,j\in\{1,2,\ldots,n\}$ $M^{(ij)}$ $\mathbb{R}^{(n+1)\times (n+1)}$ $M^{(ij)}_{ij} = T$ $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$

{M^{(i j)} : i, j \in {1, \dots, n}} .

$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$

$M \in\mathbb{R}^{(n+1)\times(n+1)}$ $M_{h,n+1} = M_{n+1,h} = 0$ $h\le n$

\sum_{i = 1}^{n} \sum_{j = 1}^{n} M_{i j} w (u_{i}, v_{j}) = T M_{n + 1, n + 1} .

$\textstyle\sum_{i=1}^n\sum_{j=1}^n M_{ij}\,w(u_i, v_j) = T\, M_{n+1,n+1}.$

$M^{(ij)}$ $M\in\mathbb{R}^{(n+1) \times (n+1)}$ $M$ $M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$ $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$

M_{n + 1, n + 1}^{'} = \sum_{i j} α_{i j} w (u_{i}, v_{j}) = \sum_{i j} M_{i j} w (u_{i}, v_{j}) / T = (T M_{n + 1, n + 1}) / T = M_{n + 1, n + 1} .

$\textstyle M'_{n+1,n+1} = \sum_{ij} \alpha_{ij} w(u_i, v_j) = \sum_{ij} M_{ij} w(u_i, v_j)/T = (T\, M_{n+1,n+1})/T = M_{n+1,n+1}.$

$G$ $T$

$G$ $T$ $M'$ $M\in\{0,1\}^{(n+1)\times (n+1)}$ $n\times n$ $M_{n+1,n+1} = 1$ $M_{h,n+1}=M_{n+1,h}=0$ $h\le n$ $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $M'$ $T$ $M_{n+1,n+1}=1$ $M$

$M$ $n+1$ $n+1$ $M_{n+1,n+1}$ $M$ $M_{n+1,n+1} = 1$ $n\times n$ $M'$ $G$ $n\times n$ $M'$ $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $T M_{n+1,n+1} = T$ $T$ $~~\Box$

Inilah bukti tertunda dari Lemma 1:

$(w,T)\in\mathbb{N}^n_+ \times \mathbb{N}_+$ $(G=(U,V,E), T)$ $U=\{u_1, u_2, \ldots, u_{2n}\}$ $V=\{v_1, v_2, \ldots, v_{2n}\}$ $i\in\{1,\ldots,n\}$ $(u_i, v_i)$ $w_i$

$T$ $S=\{i : (u_i, v_i)\in M, i\le n\}$ $M$

$S\subseteq\{1,\ldots,n\}$ $\sum_{i\in S} w_i = T$ $\{(u_i, v_i) : i \in S\}$ $T$ $T$

{(u_{i + n}, v_{i + n}) : i \in S} \cup ⋃_{i \in {1, \dots, n} ∖ S} {(u_{i}, v_{i + n}), (u_{i + n}, v_{i})} .

$\{(u_{i+n}, v_{i+n}) : i\in S\} \cup \bigcup_{i\in\{1,\ldots,n\}\setminus S}\{(u_i, v_{i+n}), (u_{i+n}, v_{i})\}.$

$~~~\Box$

ps Sebagai tambahan, menurut jawaban ini , pembatasan Matching-Sum untuk instance dengan bobot tepi terikat polinomi ada di P. Tapi saya yakin bahwa batasan masalah di pos ke matriks dengan terikat secara polinomial (bilangan bulat ) entri tetap NP sulit.

Neal Young
sumber

Sepertinya Anda mengambil lambung cembung dari matriks daripada rentang. Rentang matriks yang Anda gambarkan adalah ruang penuh matriks. Atau apakah saya melewatkan sesuatu?

Vanessa

@Quark, Anda benar - saya salah menafsirkan "span". Terima kasih. Saya mengoreksi bukti untuk menggunakan definisi rentang yang benar (seperti kombinasi linear dari matriks.)

Neal Young

M^{(i j)}

$M^{(ij)}$

w (u_{i}, v_{j})

$w(u_i,v_j)$

Poin bagus tentang membagi dengan nol. Saya akan memperbaikinya. Saya akan meninggalkan dua pengurangan terpisah, bagi saya itu lebih intuitif seperti itu.

Neal Young

$O(\sqrt{\log m})$ $m$

$P$ $P$ $-P$ $M$

\forall i^{*}, j^{*} : \sum_{i} M_{i j^{*}} = \sum_{j} M_{i^{*} j} = c

$\forall i^*, j^*: \sum_{i}{M_{ij^*}} = \sum_j{M_{i^*j}} = c$

\forall i, j : - 1 \leq M_{i j} \leq 1

$\forall i,j: -1 \leq M_{ij} \leq 1$

- 1 \leq c \leq 1

$-1 \leq c \leq 1$

Jika ini adalah representasi yang benar (tidak yakin), maka Anda bisa menambahkan batasan yang membatasi polytope ini untuk subruang yang Anda berikan. Tidak sulit untuk menyesuaikan SDP di bawah garis dengan representasi ini, tetapi saya memilih untuk tidak melewatinya untuk menjaga agar notasi dapat dikelola.

Saya tidak yakin apa perkiraan diameter untuk masalah Anda: ini mungkin memungkinkan Anda memutuskan apakah subruang yang diberikan dekat dengan matriks permutasi atau jauh dari semuanya, tapi saya belum menghitung perhitungannya.

$P = \{x: -b \leq Ax \leq b\}$ $A$ $m \times n$

$\alpha^2 = \max \sum_{i = 1}^n{\|v_i\|_2^2}$

tunduk pada:

$\forall 1 \leq i \leq m: \|\sum_{j = 1}^n{A_{ij} v_j}\|_2^2 \leq b_i^2$

Di atas rentang atas -dimensi vektor. Hal ini dapat ditulis sebagai SDP dalam cara standar dan merupakan relaksasi dari diameter , yaitu setidaknya diameter euclidean dari . $v_i$ $n$ $P$ $\alpha$ $P$

Sekarang saya mengklaim bahwa . Untuk menunjukkan ini, saya akan memberi Anda algoritma yang, diberikan dari nilai , menghasilkan panjang setidaknya . Algoritme hanyalah proyeksi acak: pilih vektor -dimensi acak di mana setiap adalah gaussian standar. Set . Menurut sifat standar gaussians: $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$ $(v_i)_{i=1}^n$ $\alpha$ $x \in P$ $\frac{\alpha}{O(\sqrt{\log m})}$ $n$ $g$ $g_i$ $\tilde{x}_i = g^T v_i$

E ‖ \tilde{x} ‖_{2}^{2} = α^{2}

$\mathbb{E}\ \|\tilde{x}\|_2^2 = \alpha^2$

\forall i \leq m : E | (A \tilde{x})_{i} |^{2} \leq b_{i}^{2} \Rightarrow E {max}_{i = 1}^{m} \frac{| (A \tilde{x})_{i} |}{b_{i}} \leq C \sqrt{\log m} .

$\forall i \leq m: \mathbb{E}\ |(A\tilde{x})_i|^2 \leq b_i^2 \ \ \Rightarrow \ \ \mathbb{E}\ \max_{i=1}^m{\frac{|(A\tilde{x})_i|}{b_i}} \leq C\sqrt{\log m}.$ di mana ikatan terakhir berlaku untuk cukup besar (ini adalah fakta standar tentang maksimum variabel acak subguassian , dan dapat dibuktikan menggunakan ikatan Chernoff).

C

$C$

m

$m$

Dua persamaan sudah menyiratkan ada sehingga dan . Atau, menggunakan batas konsentrasi, Anda dapat menunjukkan bahwa dengan probabilitas konstan dan . $x$ $x \in P$ $\|x\|_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$ $\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ $\|\tilde{x}\|_2\geq \frac{1}{2}\alpha$

Sasho Nikolov
sumber