7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Al-Mousa Jul 12 '13 at 0:47
  • 2
    $\begingroup$ 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? $\endgroup$ – András Salamon Jul 12 '13 at 10:00
  • $\begingroup$ 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}$. $\endgroup$ – Al-Mousa Jul 26 '13 at 0:49
4
$\begingroup$

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

You can download the related technical report (1990) for free.

The first paragraph from the technical report is as follows:

enter image description here

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:

enter image description here

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Al-Mousa Jul 14 '13 at 21:50
  • 2
    $\begingroup$ 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. $\endgroup$ – Abuzer Yakaryilmaz Jul 14 '13 at 22:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.