Está decidindo se alterar uma entrada diminui a permanente de uma matriz na hierarquia polinomial?

Considere o seguinte problema: dada uma matriz , índices e um número inteiro . Substituir por e chamar nova matriz . É ? $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)$

Esse problema está na hierarquia polinomial?

permanent T ....
fonte

Ele pode ser resolvido com duas chamadas para um oráculo #P ... Se estivesse no PH, isso implicaria que o PP também estivesse no PH ... No entanto, se o PP estiver no PH, o PH entraria em colapso. Então eu acho improvável que esteja no PH.

Tayfun Pay

@TayfunPay Eu não acho que esse argumento esteja correto. O problema pode ser resolvido com 2 chamadas para #P, mas não pode ser descartado tão facilmente que existe um algoritmo mais simples que pode mostrar que ele está no PH. Você teria que mostrar que é difícil para o #P, por exemplo, reduzindo Permanente a ele.

Jan Johannsen 15/02

Se você inserir a definição de permanente e simplificar a desigualdade resultante, seu problema se resume à questão de saber se a permanente de uma dada matriz (n-1) -por- (n-1) é estritamente positiva.

Gamow

@ Gamow, e vice-versa, isto é, decidir se pode ser reduzido a esse problema. Dada uma matriz , construa adicionando uma linha no topo e uma coluna à esquerda com 1 no canto superior esquerdo e 0 no caso contrário. Agora seja a matriz onde a entrada superior esquerda foi substituída por . Então por multilinearidade e desenvolvendo a primeira coluna. Assim, se o problema de Turbo em , e retornar verdadeiro.

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 15/02

@olf: Acho que você deve postar isso como resposta. Ela responde definitivamente à pergunta e, em seguida, a pergunta não aparecerá mais como "sem resposta".

Joshua Grochow 30/09

Respostas:

Seu problema é equivalente ao teste, dado , seja . $M$ $PER(M) > 0$

Prova : Suponha que você receba e deseje decidir se . Construímos seguinte forma: É fácil ver que . Agora, defina como onde substituímos a entrada de por . Por multilinearidade, segue-se que . Assim, se e somente se $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'})$

Agora vamos supor que você está dado , e e definir como na sua pergunta, ou seja, alterando para . Nós temos $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}$

onde é a matriz obtida de removendo a linha e a coluna . $M'$ $(n-1) \times (n-1)$ $M$ $i$ $j$ $\square$

holf
fonte

Boa resposta, mas provavelmente vale a pena declarar explicitamente a resposta à pergunta do OP também.

Stella Biderman