Apakah memutuskan apakah mengubah satu entri mengurangi permanen matriks dalam hierarki polinomial?

Pertimbangkan masalah berikut: diberi matriks $M\in\{-m,\dots,0,\dots,m\}^{n\times n}$ , indeks $i,j\in\{1,\dots,n\}$ dan bilangan bulat $a$ . Ganti $M[i,j]$ oleh $a$ dan panggilan baru matriks . Apakah $\hat M$ $per(M)>per(\hat M)$ ?

Apakah masalah ini dalam hierarki polinomial?

permanent T ....
sumber

Ini dapat diselesaikan dengan dua panggilan ke oracle #P ... Jika itu di PH, maka itu akan menyiratkan bahwa PP juga di PH ... Namun, jika PP di PH, maka PH runtuh. Jadi saya pikir tidak mungkin ada di PH.

Tayfun Bayar

@ PayfunPay Saya tidak berpikir argumen itu benar. Masalahnya dapat diselesaikan dengan 2 panggilan ke #P, tetapi tidak dapat dikesampingkan dengan mudah sehingga ada algoritma yang lebih sederhana yang mungkin menunjukkannya dalam PH. Anda harus menunjukkan itu sulit untuk #P untuk itu, misalnya dengan mengurangi Permanen untuk itu.

Jan Johannsen

Jika Anda memasukkan definisi permanen dan menyederhanakan ketimpangan yang dihasilkan, masalah Anda bermuara pada pertanyaan apakah permanen dari matriks yang diberikan (n-1) -dengan- (n-1) benar-benar positif.

Gamow

P E R (M) > 0

$PER(M) > 0$

M

$M$

M^{'}

$M'$

M^{″}

$M''$

M^{'}

$M'$

- 1

$-1$

P E R (M^{″}) = - P E R (M^{'}) = - P E R (M)

$PER(M'') = -PER(M') = -PER(M)$

P E R (M) > 0

$PER(M) > 0$

M^{'}

$M'$

(i, j) = (0, 0)

$(i,j) = (0,0)$

a = - 1

$a = -1$ mengembalikan true.

Serigala

@ holf: Saya pikir Anda harus memposting ini sebagai jawaban. Itu cukup definitif menjawab pertanyaan, dan kemudian pertanyaan itu tidak akan muncul sebagai "tidak dijawab" lagi.

Joshua Grochow

Jawaban:

Masalah Anda setara dengan pengujian, mengingat , apakah . $M$ $PER(M) > 0$

Bukti : Anggap Anda diberi dan Anda ingin memutuskan apakah . Kami membuat sebagai berikut: Ini adalah mudah dilihat bahwa . Sekarang, definisikan menjadi mana kita mengganti entri dengan . Dengan multilinearitas, maka . Jadi jika dan hanya jika $M$ $PER(M) > 0$ $M'$

[\begin{matrix} 1 & 0 & \dots & 0 \\ 0 \\ \dots & M \\ 0 \end{matrix}]

$\begin{bmatrix} 1 & 0 & \dots & 0 \\ 0 & & & & \\ \dots & & M & &\\ 0 & & & & \end{bmatrix}$

P E R (M) = P E R (M^{'})

$PER(M) = PER(M')$

\hat{M^{'}}

$\hat{M'}$

M^{'}

$M'$

(0, 0)

$(0,0)$

M^{'}

$M'$

- 1

$-1$

P E R (M) = P E R (M^{'}) = - P E R (\hat{M^{'}})

$PER(M) = PER(M') = -PER(\hat{M'})$

P E R (M) > 0

$PER(M) > 0$

P E R (M^{'}) > P E R (\hat{M^{'}})

$PER(M') > PER(\hat{M'})$

Sekarang asumsikan Anda diberi , dan dan mendefinisikan seperti dalam pertanyaan Anda, yaitu dengan mengubah menjadi . Kami memiliki $M$ $(i,j)$ $a$ $\hat{M}$ $M[i,j]$ $a$

\begin{aligned} P E R (M) > & P E R (\hat{M}) iff \\ \sum_{σ} \prod_{k = 1}^{n} M [k, σ (k)] > & \sum_{σ} \prod_{k = 1}^{n} \hat{M} [k, σ (k)] iff \\ \sum_{σ, σ (i) = j} M [i, j] \prod_{k \neq i}^{n} M [k, σ (k)] > & \sum_{σ, σ (i) = j} a \prod_{k \neq i}^{n} M [k, σ (k)] iff \\ (M [i, j] - a) \cdot \sum_{σ, σ (i) = j} \prod_{k \neq i}^{n} M [k, σ (k)] > & 0 iff \\ (M [i, j] - a) \cdot P E R (M^{'}) > 0 \end{aligned}

$\begin{align} PER(M) > & PER(\hat{M}) \text{ iff} \\ \sum_{\sigma} \prod_{k=1}^n M[k,\sigma(k)] > &\sum_{\sigma} \prod_{k=1}^n \hat{M}[k,\sigma(k)] \text{ iff} \\ \sum_{\sigma, \sigma(i)=j} M[i,j] \prod_{k \neq i}^n M[k,\sigma(k)] > &\sum_{\sigma, \sigma(i)=j} a \prod_{k \neq i}^n M[k,\sigma(k)] \text{ iff}\\ (M[i,j]-a) \cdot \sum_{\sigma, \sigma(i)=j} \prod_{k \neq i}^n M[k,\sigma(k)] > & 0 \text{ iff}\\ (M[i,j]-a) \cdot PER(M') > 0 \end{align}$

di mana adalah matriks yang diperoleh dari dengan menghapus baris dan kolom . $M'$ $(n-1) \times (n-1)$ $M$ $i$ $j$ $\square$

serigala
sumber

Jawaban yang bagus, tetapi mungkin layak secara eksplisit menyatakan jawaban untuk pertanyaan OP juga.

Stella Biderman