<p>Given a set of n-by-n integer matrices $\{A_1, \dots, A_m\}$, for a word $w=w_1 w_2\cdots w_l$ over $\{1, \dots, m\}$, we define $A_w:=A_{w_1}\cdots A_{w_l}$. </p>

<p>The question is to decide, given $\{A_1, \dots, A_m\}$ and a natural number $k$ <em>in binary</em>, whether there exists a word $w$ over $\{1, \dots, m\}$ whose length is bounded by $k$ such that
$[A_w]_{1,1}&gt;0$. </p>

<p>This problem is decidable, but its complexity is not clear to me. In particular, is it in PSPACE? (Note that because $k$ is given in binary, one cannot just guess a word $w$ in PSPACE.)</p>

CC BY-SA 3.0
2017-01-16T14:51:13.690Z
If $n$ is a constant, the analysis is probably simpler.  In that case, one can guess $w$ and the computation is inductively dominated by the product of two numbers of $k/2$ bits, so this should at least be in nondeterministic time bounded by $k^2$, hence NEXPTIME.  If $n$ is not constant, this should also go through, but you have to account for matrix multiplication.  Do you have any hint as of why this could go as low as PSPACE?
Michaël Cadilhac
CC BY-SA 3.0
2017-01-16T15:31:57.910Z
no, I do not have a clue. I actually want to show it is exptime-hard at least, but do not know exactly how.
maomao
CC BY-SA 3.0
2017-01-16T15:51:37.773Z
So the important condition is that k ia given in binary.
Igor Shinkar
CC BY-SA 3.0
2017-01-16T17:47:40.663Z
A related post (you might have already been aware about the content) can be found here: http://cstheory.stackexchange.com/questions/18319/complexity-of-a-variant-of-the-max-word-problem-np-complete/18322#18322
Abuzer Yakaryilmaz
CC BY-SA 3.0
2017-05-17T23:04:32.313Z
I would suspect that this is NEXP-complete (the upper bound follows from Michael's comment above). For the hardness, a much restricted variant of the unary version of this problem (same as above, but $k$ specified in unary now) with $A_i$ taken to be matrix representations of the generators of a finite group can encode subset sum/knapsack. And usually, by padding the binary version should be NEXP-hard (I'm waving my hands heavily here) Does this make sense? or is there an obvious flaw?
Nikhil
CC BY-SA 3.0
2017-05-18T09:22:26.010Z
@maomao It seems like this problem is a bounded variant of what is known in the literature as matrix mortality problem. Here is a paper that proves NP-hardness (though I'm sure with some work, the reduction from knapsack I sketched also should go through): http://www.mit.edu/~jnt/Papers/J065-97-vb-mortal.pdf. With the padding idea of Papadimitriou and Yannakkakis
Nikhil
CC BY-SA 3.0
2017-05-18T10:11:40.557Z
@maomao Oops. I'm not sure about the reduction anymore.
Nikhil
CC BY-SA 3.0
2017-05-18T10:55:18.073Z
Thanks, could you still give me the reference of the padding idea of PY?
maomao
CC BY-SA 3.0
2017-05-19T08:41:33.873Z
So their padding idea works for succinctly represented graphs. http://perso.ens-lyon.fr/natacha.portier/papers/PY86.pdf. I'm not sure if it works for any reasonable succinct encoding such as the one that pops up in the matrix mortality setting. Maybe there is a way you can adapt techniques in there to your setting (I haven't thought this through properly).
Nikhil
<cc.complexity-theory><arithmetic-circuits><pspace>
Checking a long product of matrices
maomao
# Checking a long product of matrices

(Asked by: username_0 on 2017-01-16)

Given a set of n-by-n integer matrices $\{A\_1, \dots, A\_m\}$, for a word $w=w\_1 w\_2\cdots w\_l$ over $\{1, \dots, m\}$, we define $A\_w:=A\_{w\_1}\cdots A\_{w\_l}$.

The question is to decide, given $\{A\_1, \dots, A\_m\}$ and a natural number $k$ *in binary*, whether there exists a word $w$ over $\{1, \dots, m\}$ whose length is bounded by $k$ such that
$[A\_w]\_{1,1}>0$.

This problem is decidable, but its complexity is not clear to me. In particular, is it in PSPACE? (Note that because $k$ is given in binary, one cannot just guess a word $w$ in PSPACE.)

**Tags:** cc.complexity-theory, arithmetic-circuits, pspace
> **Comments:**
> **username_1**: If $n$ is a constant, the analysis is probably simpler.  In that case, one can guess $w$ and the computation is inductively dominated by the product of two numbers of $k/2$ bits, so this should at least be in nondeterministic time bounded by $k^2$, hence NEXPTIME.  If $n$ is not constant, this should also go through, but you have to account for matrix multiplication.  Do you have any hint as of why this could go as low as PSPACE?  
> **username_0**: no, I do not have a clue. I actually want to show it is exptime-hard at least, but do not know exactly how.  
> **username_2**: So the important condition is that k ia given in binary.  
> **username_3**: A related post (you might have already been aware about the content) can be found here: http://cstheory.stackexchange.com/questions/18319/complexity-of-a-variant-of-the-max-word-problem-np-complete/18322#18322  
> **username_4**: I would suspect that this is NEXP-complete (the upper bound follows from Michael's comment above). For the hardness, a much restricted variant of the unary version of this problem (same as above, but $k$ specified in unary now) with $A_i$ taken to be matrix representations of the generators of a finite group can encode subset sum/knapsack. And usually, by padding the binary version should be NEXP-hard (I'm waving my hands heavily here) Does this make sense? or is there an obvious flaw?  
> **username_4**: @maomao It seems like this problem is a bounded variant of what is known in the literature as matrix mortality problem. Here is a paper that proves NP-hardness (though I'm sure with some work, the reduction from knapsack I sketched also should go through): http://www.mit.edu/~jnt/Papers/J065-97-vb-mortal.pdf. With the padding idea of Papadimitriou and Yannakkakis  
> **username_4**: @maomao Oops. I'm not sure about the reduction anymore.  
> **username_0**: Thanks, could you still give me the reference of the padding idea of PY?  
> **username_4**: So their padding idea works for succinctly represented graphs. http://perso.ens-lyon.fr/natacha.portier/papers/PY86.pdf. I'm not sure if it works for any reasonable succinct encoding such as the one that pops up in the matrix mortality setting. Maybe there is a way you can adapt techniques in there to your setting (I haven't thought this through properly).  

---

## 0 answers

