<p>If the number of matrices is fixed (i.e., given a part of the input), then the problem was shown to be NP-complete in <a href="http://dl.acm.org/citation.cfm?id=218895" rel="nofollow noreferrer"><em>The complexity of the max word problem and the power of one-way interactive proof systems by Condon (1993)</em></a>. </p>

<p>You can download the related <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;cad=rja&amp;ved=0CDoQFjAC&amp;url=ftp://ftp.cs.wisc.edu/pub/techreports/1990/TR952.pdf&amp;ei=JV3zUp3lJ-Sr0QXm2IDIAQ&amp;usg=AFQjCNFujOfqRB3KVDLT-x_qdqk3CPzOMQ&amp;sig2=JSMiT0Iti6dyuXtFU2wtjg&amp;bvm=bv.60799247,d.d2k" rel="nofollow noreferrer">technical report (1990) for free</a>.</p>

<p>The first paragraph from the technical report is as follows:</p>

<p><img src="https://i.sstatic.net/Q7rKn.png" alt="enter image description here"></p>

<p>Moreover, <em>the quantified max word problem for matrices</em> was recently introduced and shown to be PSPACE-complete by <a href="http://eccc.hpi-web.de/report/2014/016/" rel="nofollow noreferrer">Demirci, Say, and Yakaryilmaz (2014)</a>. Here is the related part:</p>

<p><img src="https://i.sstatic.net/dHjec.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-02-06T10:30:19.643Z
2014-02-06T11:16:09.950Z
2014-02-06T11:16:09.950Z
Abuzer Yakaryilmaz
<p><strong>If you allow the repetition of matrices</strong>, i.e. there exists $ 1 \leq i &lt; j \leq n $ s.t. $ A_i =A_j $, then your problem is actually <strong>undecidable</strong>.</p>

<p>Let $ EMPTY_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).</p>

<p>A PFA is a 4 tuple: $ P=(\Sigma,\{A_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma_1,\ldots,\sigma_k\}$ is the input alphabet, each $ A_{\sigma} $ is a stochastic matrix, $x$ is a stochastic row vector (initial distribution), and $ y $ is a zero-one column vector. Each word, say $w \in \Sigma^*$, corresponds to a sequence of the matrices from $ \{A_{\sigma \in \Sigma}\} $ by allowing repetition, and vice versa. The accepting probability of $w$ by $P$ is as follows:</p>

<p>$$f_P(w) = x \cdot A_{w_1} \cdot A_{w_2} \cdots A_{w_{|w|}} \cdot y, $$ </p>

<p>where $w_i$ is the $i^{th}$ symbol of $w$ and $|w|$ is the length of $w$.</p>

<p>$ EMPTY_{PFA} $ is the problem of, for a given PFA $ P $ and a threshold $ \lambda \in (0,1) $, whether there exists a word accepted with a probability at least $ \lambda $. $ EMPTY_{PFA} $ was shown to be undecidable. It is an old result and you can start digging from this article: <a href="http://arxiv.org/abs/quant-ph/0304082">http://arxiv.org/abs/quant-ph/0304082</a></p>

<p>$ EMPTY_{PFA} $ can be reduced to your problem. So, if your problem is decidable, then $ EMPTY_{PFA} $ is also decidable. But this is a contradiction. So, your problem is undecidable, too.</p>

CC BY-SA 3.0
2013-07-14T21:50:46.673Z
If I understood it clearly, the $EMPTY_{PFA}$ is asking for any word of any length that is accepted with probability $\lambda$. In the problem I posted, the question is given $n$, is there a word of length $n$ that is accepted with probability at least $\lambda$. Does this change the complexity?
Al-Mousa
CC BY-SA 3.0
2013-07-14T22:19:05.123Z
If the length is fixed, say $  n>0 $, then you can actually have $2^{O(n)}$ different words and so you can check one by one (or any of them nondeterministically). Then, your problem is certainly in NP.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-07-10T08:17:23.500Z
2013-07-14T21:54:21.627Z
2013-07-14T21:54:21.627Z
Abuzer Yakaryilmaz
<p>I'd like to be able to state that the following problem is NP hard.
I am wondering whether anybody have any pointers to related/recent work?</p>

<p>The problem:
Given a finite set of transition matrices $A$ and two non-negative vectors
$\vec{x}$ and $\vec{y}$. </p>

<p>Do there exist $A_1, A_2, ..., A_n \in A$ such that</p>

<p>$$\vec{x} \, A_1 \, A_2 ...  A_n \, \vec{y} \geq P$$</p>

CC BY-SA 3.0
2013-07-12T00:47:16.293Z
I made a mistake here. I want to prove that the optimisation problem is in NP, which is: Find the sequence A_1, A_2, \dots, A_n \in A that maximises x⃗ A_1 A_2...A_n y⃗. My previous question was the decision problem of this.
Al-Mousa
CC BY-SA 3.0
2013-07-12T10:00:37.377Z
Why do you think this is in NP?  (Consider: how large can a certificate proving optimality be?)  As Abuzer Yakaryilmaz points out, with repeats this is undecidable.  Are you disallowing repeats?
András Salamon
CC BY-SA 3.0
2013-07-26T00:49:42.357Z
More formally:Input: $A_1,...,A_k,x,y,P,n$
The size of the matrices are $k \times k$. $\vec{x}$ and $\vec{y}$ are vectors of size k.
and $k>>n$. How to prove that it is in NP?

 The problem is whether there exists a sequence of $n$ matrices such that
 $x B_1 B_2 ... B_n y > P$, where $B_i\in \{A_1,...,A_k\}$.


note: $k$ is fixed but it is very large ($2^d$) where $d\in \mathbb{N}$.
Al-Mousa
<cc.complexity-theory><np-hardness><matrices>
Complexity of a variant of the max word problem. NP-complete?
Al-Mousa
# Complexity of a variant of the max word problem. NP-complete?

(Asked by: username_0 on 2013-07-10)

I'd like to be able to state that the following problem is NP hard.
I am wondering whether anybody have any pointers to related/recent work?

The problem:
Given a finite set of transition matrices $A$ and two non-negative vectors
$\vec{x}$ and $\vec{y}$.

Do there exist $A\_1, A\_2, ..., A\_n \in A$ such that

$$\vec{x} \, A\_1 \, A\_2 ... A\_n \, \vec{y} \geq P$$

**Tags:** cc.complexity-theory, np-hardness, matrices
> **Comments:**
> **username_0**: I made a mistake here. I want to prove that the optimisation problem is in NP, which is: Find the sequence A_1, A_2, \dots, A_n \in A that maximises x⃗ A_1 A_2...A_n y⃗. My previous question was the decision problem of this.  
> **username_1**: Why do you think this is in NP?  (Consider: how large can a certificate proving optimality be?)  As Abuzer Yakaryilmaz points out, with repeats this is undecidable.  Are you disallowing repeats?  
> **username_0**: More formally:Input: $A_1,...,A_k,x,y,P,n$ The size of the matrices are $k \times k$. $\vec{x}$ and $\vec{y}$ are vectors of size k. and $k>>n$. How to prove that it is in NP?   The problem is whether there exists a sequence of $n$ matrices such that  $x B_1 B_2 ... B_n y > P$, where $B_i\in \{A_1,...,A_k\}$.   note: $k$ is fixed but it is very large ($2^d$) where $d\in \mathbb{N}$.  

---

## 2 answers

### Answer by username_2 on 2013-07-10. Score: 16 | Accepted answer

**If you allow the repetition of matrices**, i.e. there exists $ 1 \leq i < j \leq n $ s.t. $ A\_i =A\_j $, then your problem is actually **undecidable**.

Let $ EMPTY\_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).

A PFA is a 4 tuple: $ P=(\Sigma,\{A\_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma\_1,\ldots,\sigma\_k\}$ is the input alphabet, each $ A\_{\sigma} $ is a stochastic matrix, $x$ is a stochastic row vector (initial distribution), and $ y $ is a zero-one column vector. Each word, say $w \in \Sigma^\*$, corresponds to a sequence of the matrices from $ \{A\_{\sigma \in \Sigma}\} $ by allowing repetition, and vice versa. The accepting probability of $w$ by $P$ is as follows:

$$f\_P(w) = x \cdot A\_{w\_1} \cdot A\_{w\_2} \cdots A\_{w\_{|w|}} \cdot y, $$

where $w\_i$ is the $i^{th}$ symbol of $w$ and $|w|$ is the length of $w$.

$ EMPTY\_{PFA} $ is the problem of, for a given PFA $ P $ and a threshold $ \lambda \in (0,1) $, whether there exists a word accepted with a probability at least $ \lambda $. $ EMPTY\_{PFA} $ was shown to be undecidable. It is an old result and you can start digging from this article: <http://arxiv.org/abs/quant-ph/0304082>

$ EMPTY\_{PFA} $ can be reduced to your problem. So, if your problem is decidable, then $ EMPTY\_{PFA} $ is also decidable. But this is a contradiction. So, your problem is undecidable, too.

> **Comments:**
> **username_0**: If I understood it clearly, the $EMPTY_{PFA}$ is asking for any word of any length that is accepted with probability $\lambda$. In the problem I posted, the question is given $n$, is there a word of length $n$ that is accepted with probability at least $\lambda$. Does this change the complexity?  
> **username_2**: If the length is fixed, say $  n>0 $, then you can actually have $2^{O(n)}$ different words and so you can check one by one (or any of them nondeterministically). Then, your problem is certainly in NP.  

---

### Answer by username_2 on 2014-02-06. Score: 4

If the number of matrices is fixed (i.e., given a part of the input), then the problem was shown to be NP-complete in [*The complexity of the max word problem and the power of one-way interactive proof systems by Condon (1993)*](http://dl.acm.org/citation.cfm?id=218895).

You can download the related [technical report (1990) for free](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&ved=0CDoQFjAC&url=ftp://ftp.cs.wisc.edu/pub/techreports/1990/TR952.pdf&ei=JV3zUp3lJ-Sr0QXm2IDIAQ&usg=AFQjCNFujOfqRB3KVDLT-x_qdqk3CPzOMQ&sig2=JSMiT0Iti6dyuXtFU2wtjg&bvm=bv.60799247,d.d2k).

The first paragraph from the technical report is as follows:

![enter image description here](https://i.sstatic.net/Q7rKn.png)

Moreover, *the quantified max word problem for matrices* was recently introduced and shown to be PSPACE-complete by [Demirci, Say, and Yakaryilmaz (2014)](http://eccc.hpi-web.de/report/2014/016/). Here is the related part:

![enter image description here](https://i.sstatic.net/dHjec.png)


---

