Menemukan solusi paling sedikit untuk sistem persamaan linear

13

Seberapa sulit untuk menemukan solusi paling jarang untuk sistem persamaan linear?

Secara lebih formal, pertimbangkan masalah keputusan berikut:

Instance: Suatu sistem persamaan linear dengan koefisien integer dan angka . $c$

Pertanyaan: Apakah ada solusi untuk sistem dengan setidaknya variabel ditugaskan ke nol? $c$

Saya juga mencoba menentukan ketergantungan pada . Artinya, mungkin masalahnya adalah FPT dengan parameter . $c$ $c$

Setiap ide atau referensi sangat dihargai.

np-hardness linear-algebra linear-programming matrices sparse-matrix Michael Wehar
sumber

12

Pertimbangkan masalah untuk memaksimalkan jumlah persamaan linear yang puas pada beberapa cincin , yang sering NP-keras, misalnya dalam kasus $\text{MAX-LIN}(R)$ $R$ $R=\mathbb{Z}$

Ambil contoh dari masalah ini, mana adalah matriks. Misalkan . Bangun sistem linear baru , di mana adalah matriks , sekarang menjadi vektor dimensi, dan adalah vektor dimensi : $Ax=b$ $A$ $n\times m$ $k=m+1$ $\tilde{A}\tilde{x} = \tilde{b}$ $\tilde{A}$ $kn \times (kn+m)$ $\tilde{x}$ $(kn+m)$ $\tilde{b}$ $kn$

\tilde{A} = [\begin{matrix} A & I_{n} \\ I_{n} & - I_{n} \\ I_{n} & - I_{n} \\ ⋱ & ⋱ \\ I_{n} & - I_{n} \end{matrix}], \tilde{b} = [\begin{matrix} b \\ 0 \\ ⋮ \\ 0 \end{matrix}]

$\tilde{A} = \begin{bmatrix} A & I_n & & & \\ & I_n & -I_n & & \\ & & I_n & -I_n & \\ & & & \ddots &\ddots \\ & & & & I_n & -I_n \\ \end{bmatrix}, \tilde{b} = \begin{bmatrix} b \\ 0 \\ \vdots \\ 0 \end{bmatrix}$ mana adalah matriks identitas .

I_{n}

$I_n$

n \times n

$n \times n$

Perhatikan bahwa sistem ini selalu dipenuhi oleh vektor . Bahkan, entri pertama dari dapat berubah-ubah, dan ada beberapa vektor solusi dengan awalan itu. $\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots & b \end{pmatrix}^T$ $m$ $\tilde{x}$

Saya sekarang mengklaim bahwa pecahan persamaan dari adalah memuaskan jika jika ada solusi jarang dari yang memiliki setidaknya nol. Ini karena setiap baris puas dari menghasilkan nol potensial ketika diperluas ke $\delta$ $Ax=b$ $\tilde{A}\tilde{x}=\tilde{b}$ $\delta nk$ $Ax=b$ $k$ $x$ $\tilde{x}$

Jadi, jika kita menemukan sparsity dari solusi sparsest ke , kita juga telah memaksimalkan , dengan membagi sparsity dengan . $\tilde{A}\tilde{x}=\tilde{b}$ $\delta$ $k$

Karena itu, saya yakin masalah Anda NP-hard.

Joe Bebel
sumber

1

Keren! Terima kasih sudah berbagi. Jadi menurut Anda apa ketergantungannya pada c? Apakah Anda pikir kami dapat menyelesaikannya dalam waktu kurang dari mana adalah ukuran input?

p o l y (n) \cdot (\binom{n}{c})

$poly(n) \cdot {n \choose c}$

n

$n$

Michael Wehar

1

Tentu: jika kami menganggap Anda diberikan elemen mana dari yang nol, maka Anda dapat menghapus elemen-elemen itu dari untuk mendapatkan dimensi lebih rendah dan juga menghapus kolom yang sesuai dari untuk mendapatkan . Kemudian gunakan eliminasi gaussian untuk memutuskan apakah sistem yang direduksi layak; jika ya, maka Anda telah menemukan solusi yang jarang. Kemudian, Anda mencoba semua mungkin .

c

$c$

x

$x$

x

$x$

x^{'}

$x'$

A

$A$

A^{'}

$A'$

A^{'} x^{'} = b

$A' x' = b$

(\binom{n}{c})

$\binom{n}{c}$

A^{'} x^{'}

$A'x'$

Joe Bebel

1

@MichaelWehar Saya tidak tahu apakah masalah ini FPT atau tidak

Joe Bebel

6

Masalahnya adalah NP-lengkap, dengan pengurangan dari masalah berikut: Diberikan matriks dengan entri integer dan vektor integer dengan entri , apakah ada vektor 0-1 dengan ? $m\times n$ $A$ $b$ $n$ $x$ $Ax=b$

Untuk setiap koordinat vektor , $x_i$ $x$

perkenalkan persamaan baru dengan , dan $100(n+m)$ $x_i+y_{i,k}=0$ $k=1,\ldots,100(n+m)$
perkenalkan persamaan baru dengan . $100(n+m)$ $x_i+z_{i,k}=1$ $k=1,\ldots,100(n+m)$

Selanjutnya gunakan sistem persamaan lama . $Ax=b$

Ada solusi 0-1 untuk sistem asli , jika dan hanya jika sistem baru memiliki solusi di mana setidaknya variabel nol. $Ax=b$ $100(n+m)n$

Gamow
sumber

4

Ini disebut masalah Vektor Solusi Jarang, dan ini memang NP-hard .

BPR
sumber

4

Masalah ini sulit , dalam berbagai pengaturan. Seperti yang dinyatakan dalam jawaban lain untuk pertanyaan ini, masalahnya adalah NP-selesai atas bilangan bulat.

Dalam pemrosesan sinyal, matriks dan vektor memiliki entri rasional, dan masalah ini kadang-kadang disebut masalah rekonstruksi jarang . Dalam pengaturan ini, masalahnya adalah NP-complete (lihat Teorema 1).

Dalam teori pengkodean, entri berasal dari bidang terbatas, dan masalah ini kadang-kadang disebut masalah decoding kemungkinan maksimum . Dalam pengaturan ini, masalahnya adalah NP-lengkap dan tidak dalam waktu subeksponensial , dengan asumsi hipotesis waktu eksponensial. Selanjutnya, menurut versi sebelumnya dari kertas pada arXiv (lihat Lemma C.2 dalam versi 1 dari kertas), masalahnya adalah W [1] -complete.

argentpepper
sumber

Referensi Anda untuk W [1] -completeness tampaknya tidak memiliki "Lemma C.2".

@ RickyDemer Ada Lemma C.2 dalam versi 1 dari makalah yang dia tautkan. Namun, versi 2 tampaknya memiliki judul yang berbeda dan baru saja diubah.

Michael Wehar

Lemma itu menggunakan parameterisasi yang berbeda dari OP.

Oh saya tidak menyadari ada versi yang diperbarui, saya akan melihatnya dan memperbarui jawaban saya sesuai.

argentpepper

Seperti yang saya sebutkan di komentar saya sebelumnya, bahwa "lemma menggunakan parameterisasi yang berbeda dari OP", jadi bahkan jika kita menganggap hasilnya benar (meskipun telah dihapus dari versi 2), pertanyaan OP tentang kompleksitas parameterisasi masih akan terbuka.

Menemukan solusi paling sedikit untuk sistem persamaan linear

Jawaban: