Kompleksitas masalah matriks

Masalah berikut baru-baru ini muncul dalam penelitian saya. Menjadi tidak ahli dalam pertanyaan algoritmik, saya telah mencari Google secara ekstensif dalam mencari masalah yang cocok untuk dikurangi. Saya tidak melihat bagaimana 3SAT akan bekerja, dan meskipun ZOE memiliki semangat yang sama, pengurangannya tidak terlihat jelas. Kemungkinan lain adalah teori eksistensial real. Sepertinya itu juga bukan pertandingan yang tepat, tetapi saya mungkin salah tentang itu.

Masalah: $A$ dan $B$ keduanya $n\times n$ -harga di bidang favorit Anda. Kami berasumsi bahwa set indeks $A$ yang sewenang-wenang diatur ke 0. Demikian juga, set indeks $B$ yang sewenang-wenang diatur ke 0. Pertanyaan: dapatkah kita mengisi indeks $A$ dan $B$ yang tersisa sehingga $AB = I_n$ ?

Contoh: $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$ , $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$ . Tidak memungkinkan.

Apa kompleksitas komputasi ini (dalam $n$ )?

Setiap petunjuk atau ide ke mana harus mencari hasil yang sama dalam literatur akan sangat dihargai.

EDIT (benar-benar lupa tentang posting ini): Dalam karya terbaru yang tersedia di arXiv (jika ada yang tertarik preprint beritahu saya) kami telah menunjukkan bahwa masalahnya adalah NP-keras selama setiap bidang yang terbatas.

cc.complexity-theory MB
sumber

Asalkan bidang dasar cukup besar, masalah memeriksa apakah Anda dapat membuat

dapat direduksi menjadi (pelengkap) pengujian identitas polinomial. Perhatikan bahwa penentu

adalah polinomial dalam nilai entri yang hilang.

A B

$AB$

A B

$AB$

Andrew Morgan

Juga, kasus di mana kita membatasi entri

dan

menjadi nol-satu, dan karakteristik bidang lebih besar dari

, berkurang menjadi pencocokan sempurna bipartit. Anda dapat membayangkan memilih untuk setiap indeks

indeks lain

sehingga Anda menetapkan

dan entri sisanya nol. (Menempatkan lebih banyak dari ini hanya bisa menyakitkan.) Maka kondisi

dapat dinyatakan sebagai grafik bipartit dengan indeks

A

$A$

B

$B$

n

$n$

i

$i$

k_{i}

$k_i$

A_{i, k_{i}} = B_{k_{i}, i} = 1

$A_{i,k_i} = B_{k_i,i} = 1$

A B = I_{n}

$AB = I_n$

i

$i$ di sebelah kiri, pilihan

di kanan, dan tepi untuk

pasangan yang dapat kita atur

dan

k_{i}

$k_i$

(i, k_{i})

$(i,k_i)$

A_{i, k_{i}}

$A_{i,k_i}$

B_{k_{i}, i}

$B_{k_i,i}$

Andrew Morgan

@MB: Juga, perhatikan bahwa saat memeriksa jika

dapat dibuat dibalik sama dengan memeriksa apakah kedua

dan

dapat, secara terpisah, dibuat dibalik, memeriksa apakah

dapat dibuat dibalik tidak sama seperti memeriksa apakah

dapat dibuat identitas . Untuk memeriksa apakah

(resp.

) dapat dibuat tidak dapat dibalik, Anda mengatakan "itu dapat dilakukan secara efektif," tetapi dalam pengaturan Anda ini sama dengan memeriksa kecocokan sempurna di antara dukungan

(resp.

A B

$AB$

A

$A$

B

$B$

A B

$AB$

A B

$AB$

A

$A$

B

$B$

A

$A$

B

$B$ ) (masalah yang sama, tetapi pengaturan yang sedikit berbeda dari komentar kedua Andrew Morgan).

Joshua Grochow

Beberapa kasus khusus dari masalah ini tampaknya mungkin terjadi dalam PPAD, seperti Masalah Kelengkapan Linear: kintali.wordpress.com/2009/08/04/linear-complementarityarity-prob‌ lem Ini akan menunjukkan bahwa menemukan solusi itu sulit.

domotorp

Jika yang lain belum menemukan jawabannya, ada pilihan

(di atas bidang apa pun) yang

, tetapi gagal untuk tes pencocokan sempurna. yaitu tidak ada permutasi matriks

sehingga

didukung pada dukungan

, dan

didukung pada dukungan

. Pilihan diberikan oleh

dan

A, B

$A,B$

A B = I

$AB = I$

P

$P$

P

$P$

A

$A$

P^{- 1} = P^{⊺}

$P^{-1}=P^{\intercal}$

B

$B$

A = [\begin{matrix} 1 & - 1 & 0 \\ 1 & 0 & 1 \\ 1 & - 1 & 1 \end{matrix}]

$A=\begin{bmatrix}1&-1&0\\1&0&1\\1&-1&1\end{bmatrix}$

B = [\begin{matrix} 1 & 1 & - 1 \\ 0 & 1 & - 1 \\ - 1 & 0 & 1 \end{matrix}]

$B=\begin{bmatrix}1&1&-1\\0&1&-1\\-1&0&1\end{bmatrix}$

Andrew Morgan

Nah, di sini adalah tidak-mengerikan atas terikat lebih : , atau dengan asumsi Hipotesis Riemann, . Ini karena untuk setiap pola nol yang diberikan untuk , memeriksa apakah seseorang dapat membuat memeriksa apakah sistem tertentu dari persamaan bilangan bulat integer memiliki solusi dalam , dan ini dapat dilakukan di bagian atas ini. batas, oleh Koiran. $\mathbb{C}$ $\mathsf{PSPACE}$ $\mathsf{AM}$ $A,B$ $AB=I_n$ $n^2$ $\mathbb{C}$

Pendekatan lain adalah mencoba memanfaatkan fakta bahwa ini sebenarnya adalah sistem persamaan bilinear . Memecahkan persamaan bilinear sama dengan menemukan solusi "peringkat 1" untuk persamaan linear. Saya sudah mencoba untuk menentukan apakah ada batas atas yang lebih baik untuk menyelesaikan sistem bilinear secara umum, tetapi sejauh ini tidak berhasil. Mungkin juga seseorang dapat memanfaatkan struktur tertentu dari persamaan bilinear ini untuk mendapatkan sesuatu yang lebih baik daripada yang diketahui secara umum ...

Joshua Grochow
sumber

Tidakkah PSPACE mengikuti dari masalah yang ada dalam NP?

@ MB: Lebih dari bidang terbatas masalah jelas dalam NP (hanya menunjukkan pengaturan variabel), yang merupakan batas atas yang lebih baik daripada AM, bahkan. Ketika input polinomial bilangan bulat tetapi Anda meminta solusi dalam bilangan kompleks, ketika ada solusi, bahkan tidak jelas bahwa Anda dapat menuliskannya dalam jumlah memori terbatas, apalagi dibatasi secara polinomi.

Joshua Grochow

Kompleksitas masalah matriks

Jawaban: