Problema de mortalidad matricial

En informática , el problema de la mortalidad matricial (o problema de la matriz mortal ) es un problema de decisión que pregunta, dado un conjunto de tamaño m de matrices n × n con coeficientes enteros, si la matriz cero se puede expresar como un producto finito de matrices de este conjunto.

Se sabe que el problema de mortalidad de matrices es indecidible cuando n ≥ 3. ^{[ 1 ]} De hecho, ya es indecidible para conjuntos de 6 matrices (o más) cuando n = 3, para 4 matrices cuando n = 5, para 3 matrices cuando n = 9 y para 2 matrices cuando n = 15. ^{[ 2 ]}

En el caso n = 2, es un problema abierto si la mortalidad de matrices es decidible, pero se han resuelto varios casos especiales: el problema es decidible para conjuntos de 2 matrices, ^{[ 3 ]} y para conjuntos de matrices que contienen como máximo una matriz invertible. ^{[ 4 ]}

• Bell, Paul; Potapov, Igor (4 de febrero de 2008). "Sobre los límites de indecidibilidad para problemas de decisión matricial" . Theoretical Computer Science . Combinatorics, Automata and Number Theory. 391 (1): 3– 13. doi : 10.1016/j.tcs.2007.10.025 . ISSN 0304-3975 . 
• Halava, Vesa (agosto de 1997). Problemas decidibles e indecidibles en la teoría de matrices (Informe). Centro de Ciencias de la Computación de Turku.>