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.)

  • 1
    $\begingroup$ 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? $\endgroup$ Jan 16 '17 at 14:51
  • $\begingroup$ no, I do not have a clue. I actually want to show it is exptime-hard at least, but do not know exactly how. $\endgroup$
    – maomao
    Jan 16 '17 at 15:31
  • $\begingroup$ So the important condition is that k ia given in binary. $\endgroup$ Jan 16 '17 at 15:51
  • 2
    $\begingroup$ A related post (you might have already been aware about the content) can be found here: cstheory.stackexchange.com/questions/18319/… $\endgroup$ Jan 16 '17 at 17:47
  • 1
    $\begingroup$ 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? $\endgroup$
    – Nikhil
    May 17 '17 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.