Complexité d'un problème matriciel

Le problème suivant est récemment apparu dans mes recherches. N'étant pas un expert des questions algorithmiques, j'ai beaucoup recherché sur Google dans la recherche de problèmes appropriés à réduire. Je ne vois pas comment 3SAT fonctionnerait, et même si ZOE est similaire dans l'esprit, une réduction n'est pas évidente. Une autre possibilité serait la théorie existentielle des réels. Cela ne semble pas être tout à fait le match non plus, mais je peux me tromper à ce sujet.

Problème: et sont tous deux matrices sur votre champ préféré. Nous supposons qu'un ensemble arbitraire d'indices de est défini sur 0. De même, un ensemble arbitraire d'indices de est défini sur 0. Question: pouvons-nous remplir les indices restants de et tels que ? $A$ $B$ $n\times n$ $A$ $B$ $A$ $B$ $AB = I_n$

Exemple: , . Pas possible. $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$ $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$

Quelle est la complexité de calcul de ceci (en )? $n$

Tous les conseils ou idées où chercher des résultats similaires dans la littérature seront grandement appréciés.

EDIT (complètement oublié ce message): Dans des travaux récents disponibles sur l'arXiv (si quelqu'un est intéressé par la préimpression, faites-le moi savoir), nous avons montré que le problème est NP-difficile sur tout champ fini.

cc.complexity-theory MB
la source

Pourvu que le champ de base soit suffisamment grand, le problème de vérifier si vous pouvez rendre inversible se réduit à (le complément des) tests d'identité polynomiale. Il suffit d'observer que le déterminant de est un polynôme dans les valeurs des entrées manquantes.

A B

$AB$

A B

$AB$

Andrew Morgan

De plus, le cas où nous restreignons les entrées de et à zéro, et où la caractéristique du champ est supérieure à , se réduit à une correspondance parfaite bipartite. Vous pouvez imaginer choisir pour chaque index un autre index afin de définir et les entrées restantes zéro. (En mettre plus que cela ne peut que nuire.) Alors la condition peut être exprimée sous forme de graphe bipartite avec les indices à gauche, les choix de à droite et les arêtes des paires pour lesquelles nous pouvons définir et

A

$A$

B

$B$

n

$n$

i

$i$

k_{i}

$k_i$

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

$A_{i,k_i} = B_{k_i,i} = 1$

A B = I_{n}

$AB = I_n$

i

$i$

k_{i}

$k_i$

(i, k_{i})

$(i,k_i)$

A_{i, k_{i}}

$A_{i,k_i}$

B_{k_{i}, i}

$B_{k_i,i}$ .

Andrew Morgan

@MB: Notez également que vérifier si peut être rendu inversible revient à vérifier si et peuvent être rendus inversibles séparément, vérifier si peut être rendu inversible n'est pas la même chose que vérifier si peut se faire l'identité . Pour vérifier si (resp. ) peut être rendu inversible, vous dites "cela peut être fait efficacement", mais dans votre configuration cela équivaut à vérifier une correspondance parfaite entre le support de (resp. ) (même problème , mais réglage légèrement différent du deuxième commentaire d'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 du

Un cas particulier de ce problème semble probable dans PPAD, comme le problème de complémentarité linéaire: kintali.wordpress.com/2009/08/04/linear-complementarity-prob‌ lem Cela montrerait qu'il est difficile de trouver une solution.

domotorp

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

Eh bien, voici une limite supérieure non horrible sur : , ou en supposant l'hypothèse de Riemann, . En effet, pour tout modèle de zéros donné pour , vérifier si l'on peut faire revient à vérifier si un certain système d' équations polynomiales entières a une solution dans , et cela peut être fait dans ces limites supérieures, par Koiran. $\mathbb{C}$ $\mathsf{PSPACE}$ $\mathsf{AM}$ $A,B$ $AB=I_n$ $n^2$ $\mathbb{C}$

Une autre approche consiste à essayer de tirer parti du fait qu'il s'agit en fait d'un système d' équations bilinéaires . La résolution d'équations bilinéaires équivaut à trouver des solutions de «rang 1» aux équations linéaires. J'ai essayé de déterminer s'il existe de meilleures limites supérieures pour résoudre les systèmes bilinéaires en général, mais sans succès jusqu'à présent. Il est également possible que l'on puisse tirer parti de la structure particulière de ces équations bilinéaires pour obtenir quelque chose de mieux que ce qui est connu en général ...

Joshua Grochow
la source

PSPACE ne découle-t-il pas du problème de NP?

@MB: Sur les champs finis, le problème est évidemment dans NP (montrez simplement le réglage des variables), ce qui est une meilleure limite supérieure que AM, même. Lorsque l'entrée est des polynômes entiers mais que vous demandez une solution dans les nombres complexes, quand il y a une solution, il n'est même pas évident que vous pouvez l'écrire dans une quantité finie de mémoire, sans parler de limites polynomiales.

Joshua Grochow

Complexité d'un problème matriciel

Réponses: