¿Decidir si cambiar una entrada disminuye el permanente de una matriz en la jerarquía polinómica?

Considere el siguiente problema: dada una matriz , índices y un número entero . Reemplazar por y llame nueva matriz . Es $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)$

¿Es este problema en la jerarquía polinómica?

permanent T ....
fuente

Se puede resolver con dos llamadas a un oráculo #P ... Si estaba en PH, entonces implicaría que PP también está en PH ... Sin embargo, si PP está en PH, entonces PH colapsa. Así que creo que es poco probable que esté en PH.

Tayfun paga

@TayfunPay No creo que ese argumento sea correcto. El problema se puede resolver con 2 llamadas a #P, pero no se puede descartar tan fácilmente que hay un algoritmo más simple que puede mostrar que está en PH. Tendría que mostrar que es difícil para #P para eso, por ejemplo, reduciendo Permanente.

Jan Johannsen

Si conecta la definición del permanente y simplifica la desigualdad resultante, su problema se reduce a la pregunta de si el permanente de una matriz dada (n-1) -por- (n-1) es estrictamente positivo.

Gamow

@Gamow, y viceversa, es decir, decidir si

puede reducirse a este problema. Dada una matriz

, construya

agregando una línea en la parte superior y una columna a la izquierda con un 1 en la esquina superior izquierda y 0 en caso contrario. Ahora deje que

sea la matriz

donde la entrada superior izquierda ha sido reemplazada por

. Entonces

P E R (M) > 0

$PER(M) > 0$

M

$M$

M^{'}

$M'$

M^{″}

$M''$

M^{'}

$M'$

- 1

$-1$

por multilinealidad y desarrollando la primera columna. Por lo tanto,

si el problema de Turbo en

devuelve verdadero.

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: Creo que deberías publicar esto como respuesta. Responde definitivamente la pregunta, y luego la pregunta ya no aparecerá como "sin respuesta".

Joshua Grochow

Respuestas:

Su problema es equivalente a probar, dado $M$ , si $PER(M) > 0$ .

Prueba : Suponga que recibe $M$ y desea decidir si $PER(M) > 0$ . Construimos $M'$ como sigue:

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

$\begin{bmatrix} 1 & 0 & \dots & 0 \\ 0 & & & & \\ \dots & & M & &\\ 0 & & & & \end{bmatrix}$ Es fácil ver que

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

$PER(M) = PER(M')$ . Ahora, defina

\hat{M^{'}}

$\hat{M'}$ como

M^{'}

$M'$ donde reemplazamos la entrada

(0, 0)

$(0,0)$ de

M^{'}

$M'$ por

- 1

$-1$ . Por multilinealidad, se deduce que

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

$PER(M) = PER(M') = -PER(\hat{M'})$ . Por lo tanto,

P E R (M) > 0

$PER(M) > 0$ si y solo si

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

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

$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}$

$M'$ $(n-1) \times (n-1)$ $M$ $i$ $j$ $\square$

holf
fuente

Buena respuesta, pero probablemente también valga la pena indicar explícitamente la respuesta a la pregunta del OP.

Stella Biderman