# Complexity of a variant of the max word problem. NP-complete?

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

• 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. Jul 12 '13 at 0:47
• 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? Jul 12 '13 at 10:00
• 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}$. Jul 26 '13 at 0:49

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

The first paragraph from the technical report is as follows:

Moreover, the quantified max word problem for matrices was recently introduced and shown to be PSPACE-complete by Demirci, Say, and Yakaryilmaz (2014). Here is the related part:

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.

• 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? Jul 14 '13 at 21:50
• 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. Jul 14 '13 at 22:19