Complexidade de um problema de matriz

O seguinte problema apareceu recentemente em minha pesquisa. Como não sou especialista em questões algorítmicas, pesquisei bastante no Google em busca de problemas adequados para reduzir. Não vejo como o 3SAT funcionaria e, embora o ZOE seja semelhante em espírito, uma redução não é óbvia. Outra possibilidade seria a teoria existencial dos reais. Isso também não parece bem, mas eu posso estar errado sobre isso.

Problema: e são -matrices sobre seu campo favorito. Assumimos que um conjunto arbitrário de índices de seja definido como 0. Da mesma forma, um conjunto arbitrário de índices de é definido como 0. Pergunta: podemos preencher os índices restantes de e modo que ? $A$ $B$ $n\times n$ $A$ $B$ $A$ $B$ $AB = I_n$

Exemplo: $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$ , $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$ . Não é possivel.

Qual é a complexidade computacional disso (em $n$ )?

Qualquer sugestão ou idéia sobre onde procurar resultados semelhantes na literatura será muito apreciada.

EDIT (esqueci completamente deste post): Em um trabalho recente que está disponível no arXiv (se alguém estiver interessado na pré-impressão, avise-me), mostramos que o problema é difícil para NP em qualquer campo finito.

cc.complexity-theory MB
fonte

Desde que o campo base seja grande o suficiente, o problema de verificar se você pode tornar o

A B

$AB$ invertível se reduz a (o complemento do) teste de identidade polinomial. Apenas observe que o determinante de

A B

$AB$ é um polinômio nos valores das entradas ausentes.

Andrew Morgan

Além disso, o caso em que restringimos as entradas de

A

$A$ e

B

$B$ a zero e a característica do campo é maior que

n

$n$ , reduz-se à correspondência perfeita bipartida. Você pode imaginar escolher para cada índice

i

$i$ outro índice

k_{i}

$k_i$ para definir

A_{i, k_{i}} = B_{k_{i}, i} = 1

$A_{i,k_i} = B_{k_i,i} = 1$ e as entradas restantes zero. (Colocar mais do que isso só pode prejudicar.) Então a condição

A B = I_{n}

$AB = I_n$ pode ser expressa como um gráfico bipartido com os índices

i

$i$ à esquerda, opções de

k_{i}

$k_i$ à direita e arestas para pares

(i, k_{i})

$(i,k_i)$ para os quais podemos definir

A_{i, k_{i}}

$A_{i,k_i}$ e

B_{k_{i}, i}

$B_{k_i,i}$ .

Andrew Morgan

@MB: Observe também que, ao verificar se pode ser tornado invertível, é o mesmo que verificar se e , separadamente, podem ser invertidos, verificar se pode ser invertido não é o mesmo que verificar se pode ser feita a identidade . Para verificar se (resp. ) pode ser invertido, você diz "isso pode ser feito com eficiência", mas na sua configuração isso é equivalente a verificar se há uma correspondência perfeita entre o suporte de (resp. ) (mesmo problema , mas um pouco diferente do segundo comentário de Andrew Morgan).

A B

$AB$

A

$A$

B

$B$

A B

$AB$

A B

$AB$

A

$A$

B

$B$

A

$A$

B

$B$

Joshua Grochow

É provável que algum caso especial desse problema ocorra no PPAD, como o problema de complementaridade linear: kintali.wordpress.com/2009/08/04/linear-complementarity-prob‌ lem Isso mostra que é difícil encontrar uma solução.

Domotorp 29/10

Caso outros ainda não tenham entendido isso, há uma opção de (em qualquer campo) para a qual , mas para a qual o teste de correspondência perfeita falha. isto é, não há nenhuma matriz de permutação de modo que é suportada no suporte de , e é suportada no suporte de . A escolha é dada por e .

A, B

$A,B$

A B = I

$AB = I$

P

$P$

P

$P$

A

$A$

P^{- 1} = P^{⊺}

$P^{-1}=P^{\intercal}$

B

$B$

A = [\begin{matrix} 1 & - 1 & 0 \\ 1 & 0 & 1 \\ 1 & - 1 & 1 \end{matrix}]

$A=\begin{bmatrix}1&-1&0\\1&0&1\\1&-1&1\end{bmatrix}$

B = [\begin{matrix} 1 & 1 & - 1 \\ 0 & 1 & - 1 \\ - 1 & 0 & 1 \end{matrix}]

$B=\begin{bmatrix}1&1&-1\\0&1&-1\\-1&0&1\end{bmatrix}$

Andrew Morgan

Bem, aqui está um limite superior não horrível sobre : , ou assumindo a hipótese de Riemann, . Isso ocorre porque, para qualquer padrão de zeros para , verificar se é possível criar está verificando se um determinado sistema de equações polinomiais inteiras tem uma solução em , e isso pode ser feito nesses limites superiores, por Koiran. $\mathbb{C}$ $\mathsf{PSPACE}$ $\mathsf{AM}$ $A,B$ $AB=I_n$ $n^2$ $\mathbb{C}$

Outra abordagem é tentar aproveitar o fato de que este é de fato um sistema de equações bilineares . Resolver equações bilineares é equivalente a encontrar soluções de "classificação 1" para equações lineares. Eu tenho tentado determinar se existem melhores limites superiores para resolver sistemas bilineares em geral, mas sem sorte até agora. Também é possível que alguém possa aproveitar a estrutura específica dessas equações bilineares para obter algo melhor do que se sabe em geral ...

Joshua Grochow
fonte

O PSPACE não segue o problema de estar no NP?

@ MB: Em campos finitos, o problema está obviamente em NP (apenas mostre a configuração das variáveis), que é um limite superior melhor que o AM, mesmo. Quando a entrada é polinômio inteiro, mas você pede uma solução nos números complexos, quando existe uma solução, nem é óbvio que você pode anotá-la em qualquer quantidade finita de memória, sem falar em limites polinomiais.

Joshua Grochow 31/10

Complexidade de um problema de matriz

Respostas: