Wird durch die Entscheidung, ob durch Ändern eines Eintrags die Permanente einer Matrix in der Polynomhierarchie verringert wird?

Betrachten Sie das folgende Problem: gegeben eine Matrix , Indizes und eine ganze Zahl . Ersetzen durch neue Matrix nennen . Ist $M\in\{-m,\dots,0,\dots,m\}^{n\times n}$ $i,j\in\{1,\dots,n\}$ $a$ $M[i,j]$ $a$ $\hat M$ ? $per(M)>per(\hat M)$

Liegt dieses Problem in der Polynomhierarchie?

permanent T ....
quelle

Es kann durch zwei Aufrufe eines # P-Orakels gelöst werden ... Wenn es in PH wäre, würde dies bedeuten, dass PP auch in PH ist ... Wenn sich PP jedoch in PH befindet, bricht PH zusammen. Daher halte ich es für unwahrscheinlich, dass es sich um eine PH handelt.

Tayfun Pay

@TayfunPay Ich denke nicht, dass dieses Argument richtig ist. Das Problem kann mit 2 Aufrufen von #P gelöst werden, aber es kann nicht so einfach ausgeschlossen werden, dass es einen einfacheren Algorithmus gibt, der möglicherweise anzeigt, dass es sich um PH handelt. Sie müssten zeigen, dass es für #P schwierig ist, z. B. indem Sie Permanent darauf reduzieren.

Jan Johannsen

Wenn Sie die Definition der Permanente einfügen und die resultierende Ungleichung vereinfachen, läuft Ihr Problem auf die Frage hinaus, ob die Permanente einer gegebenen (n-1) -by- (n-1) -Matrix streng positiv ist.

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$ gibt true zurück.

Holf

@holf: Ich denke du solltest dies als Antwort posten. Es beantwortet die Frage ziemlich definitiv, und dann wird die Frage nicht mehr als "unbeantwortet" angezeigt.

Joshua Grochow

Antworten:

Ihr Problem entspricht dem Testen bei , ob . $M$ $PER(M) > 0$

Beweis : Angenommen, Sie erhalten und möchten entscheiden, ob . Wir konstruieren wie folgt: Es ist leicht zu erkennen, dass . Definieren Sie nun als wobei wir den -Eintrag von durch ersetzen . Aus der Multilinearität folgt, dass . Also genau dann, wenn $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'})$

Nehmen wir nun an, Sie erhalten , und und definieren wie in Ihrer Frage, dh indem Sie in ändern . Wir haben $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}$

wobei die Matrix ist, die aus durch Entfernen der Linie und der Spalte . $M'$ $(n-1) \times (n-1)$ $M$ $i$ $j$ $\square$

holf
quelle

Gute Antwort, aber es lohnt sich wahrscheinlich, die Antwort auch auf die Frage des OP explizit anzugeben.

Stella Biderman