Décider si la modification d'une entrée diminue le permanent d'une matrice dans la hiérarchie polynomiale?

Considérons le problème suivant: étant donné une matrice , les indices et un entier . Remplacer par et appeler nouvelle matrice . Est-ce que ? $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)$

Ce problème est-il dans la hiérarchie polynomiale?

permanent T ....
la source

Il peut être résolu par deux appels à un oracle #P ... S'il était en PH, cela impliquerait que PP est également en PH ... Cependant, si PP est en PH, alors PH s'effondre. Je pense donc qu'il est peu probable que ce soit en PH.

Tayfun Pay du

@TayfunPay Je ne pense pas que cet argument soit correct. Le problème peut être résolu avec 2 appels à #P, mais il ne peut pas être écarté si facilement qu'il existe un algorithme plus simple qui pourrait montrer qu'il est en PH. Il faudrait montrer que c'est difficile pour #P pour cela, par exemple en y réduisant Permanent.

Jan Johannsen

Si vous branchez la définition du permanent et simplifiez l'inégalité qui en résulte, votre problème se résume à la question de savoir si le permanent d'une matrice donnée (n-1) -par- (n-1) est strictement positif.

Gamow

@Gamow, et inversement, c'est-à-dire décider si peut être réduit à ce problème. Étant donné une matrice , construisez en ajoutant une ligne en haut et une colonne à gauche avec un 1 dans le coin supérieur gauche et 0 sinon. Soit maintenant la matrice où l'entrée en haut à gauche a été remplacée par . Puis par multilinéarité et développement de la première colonne. Ainsi si le problème de Turbo sur , et renvoie vrai.

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$

holf

@holf: Je pense que vous devriez poster ceci comme réponse. Il répond assez définitivement à la question, puis la question n'apparaîtra plus comme "sans réponse".

Joshua Grochow

Réponses:

Votre problème équivaut à tester, étant donné , que . $M$ $PER(M) > 0$

Preuve : Supposons que l'on vous donne et que vous souhaitez décider si . Nous construisons comme suit: C'est facile à voir que . Maintenant, définissez comme étant où nous remplaçons l' entrée de par . Par multilinéarité, il s'ensuit que . Ainsi si et seulement si $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'})$

Supposons maintenant qu'on vous donne , et et définissons comme dans votre question, c'est-à-dire en changeant en . Nous avons $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}$

où est la matrice obtenue à partir de en supprimant la ligne et la colonne . $M'$ $(n-1) \times (n-1)$ $M$ $i$ $j$ $\square$

loup
la source

Bonne réponse, mais cela vaut probablement la peine de mentionner explicitement la réponse à la question du PO.

Stella Biderman