<p>A discrete-time Markov chain (DTMC) is a tuple $M=(S,s_{init},P)$ where $S$ is a finite set of states, $s_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability matrix.</p>

<p>For a subset $S'\subseteq S$ with $s_{init},t\in S'$ we define the induced sub-DTMC $M_{S'}=(S',s_{init},P')$ with $P'(s,s')=P(s,s')$ for all $s,s'\in S'$.
If the sum of the out-going probabilities of a state $s\in S'$ is less than 1, a deadlock state is entered with probability $1-\sum_{s'\in S'}P(s,s')$ such that $t$ cannot be reached anymore.</p>

<p>Assume we are given a DTMC $M=(S,s_{init},P)$ and a target state $t\in S$ such that the probability to finally reach $t$ from $s_{init}$ is larger than a given bound $\lambda$. We are interested in subsets $S'\subseteq S$ with $s_{init},t\in S'$ such that the probability of reaching $t$ from $s_{init}$ in $M_{S'}$ is still larger than $\lambda$.</p>

<p>Question: What is the complexity of deciding whether there is such a $S'$ containing at most $k$ states (for a given $k$)?</p>

<p>We suppose that this problem is NP-complete (obviously it is in NP: guess an appropriate $S'$ and compute the reachability probabilities to check if the bound $\lambda$ is exceeded; this can be done by solving a linear equation system). However, we have not found a reduction to show the NP-hardness. Maybe someone can help ...</p>

<hr />

<p>For Markov decision processes, which feature non-deterministic choices in addition to the probabilistic choices of DTMCs, the same problem has been proven to be NP-complete, see</p>

<p>Chadha, Viswanathan - <i>A counterexample-guided abstraction-refinement framework for Markov decision processes</i>, ACM Trans. Comput. Log. 12(1), 2010
<a href="http://dl.acm.org/citation.cfm?doid=1838552.1838553" rel="nofollow">http://dl.acm.org/citation.cfm?doid=1838552.1838553</a></p>

<p>The same holds also for DTMCs and PCTL properties, if <i>nested</i> formulae are allowed. However, for pure reachability I was not able to find a proof for NP-hardness.</p>

CC BY-SA 3.0
2012-08-31T16:41:42.313Z
I do not know how you interpret M_{S′} as a Markov chain, because the probabilities of transition from s to s′ do not sum to 1 when summed over s′∈S′.  Do you renormalize the probabilities, or do you consider everything outside S′ as a blackhole?
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-31T16:59:42.870Z
If the out-going probabilities of a state $s$ do not sum up to 1, you run into a deadlock with probability $1-\sum_{s'\in S'}P(s,s')$.
Roffle
CC BY-SA 3.0
2012-08-31T17:00:35.637Z
Please edit your question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-31T21:34:35.447Z
And "deadlocking" is equivalent to moving along a self-loop of the current vertex so that in the next time step, there is the possibility of leaving this vertex or is "deadlocking" equivalent to moving to a new sink vertex who's only outgoing edge is a self-loop and is taken with probability 1?
Tyson Williams
CC BY-SA 3.0
2012-08-31T21:40:06.767Z
@Tyson: I did not realize the possibility of the former interpretation, but that is a good point.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-01T06:54:26.707Z
No, deadlocking is equivalent to moving to a absorbing state from which the target state $t$ cannot be reached.
Roffle
<cc.complexity-theory><np-hardness><markov-chains>
Complexity of DTMC subsystems
Roffle
# Complexity of DTMC subsystems

(Asked by: username_0 on 2012-08-31)

A discrete-time Markov chain (DTMC) is a tuple $M=(S,s\_{init},P)$ where $S$ is a finite set of states, $s\_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability matrix.

For a subset $S'\subseteq S$ with $s\_{init},t\in S'$ we define the induced sub-DTMC $M\_{S'}=(S',s\_{init},P')$ with $P'(s,s')=P(s,s')$ for all $s,s'\in S'$.
If the sum of the out-going probabilities of a state $s\in S'$ is less than 1, a deadlock state is entered with probability $1-\sum\_{s'\in S'}P(s,s')$ such that $t$ cannot be reached anymore.

Assume we are given a DTMC $M=(S,s\_{init},P)$ and a target state $t\in S$ such that the probability to finally reach $t$ from $s\_{init}$ is larger than a given bound $\lambda$. We are interested in subsets $S'\subseteq S$ with $s\_{init},t\in S'$ such that the probability of reaching $t$ from $s\_{init}$ in $M\_{S'}$ is still larger than $\lambda$.

Question: What is the complexity of deciding whether there is such a $S'$ containing at most $k$ states (for a given $k$)?

We suppose that this problem is NP-complete (obviously it is in NP: guess an appropriate $S'$ and compute the reachability probabilities to check if the bound $\lambda$ is exceeded; this can be done by solving a linear equation system). However, we have not found a reduction to show the NP-hardness. Maybe someone can help ...

---

For Markov decision processes, which feature non-deterministic choices in addition to the probabilistic choices of DTMCs, the same problem has been proven to be NP-complete, see

Chadha, Viswanathan - *A counterexample-guided abstraction-refinement framework for Markov decision processes*, ACM Trans. Comput. Log. 12(1), 2010
<http://dl.acm.org/citation.cfm?doid=1838552.1838553>

The same holds also for DTMCs and PCTL properties, if *nested* formulae are allowed. However, for pure reachability I was not able to find a proof for NP-hardness.

**Tags:** cc.complexity-theory, np-hardness, markov-chains
> **Comments:**
> **username_1**: I do not know how you interpret M_{S′} as a Markov chain, because the probabilities of transition from s to s′ do not sum to 1 when summed over s′∈S′.  Do you renormalize the probabilities, or do you consider everything outside S′ as a blackhole?  
> **username_0**: If the out-going probabilities of a state $s$ do not sum up to 1, you run into a deadlock with probability $1-\sum_{s'\in S'}P(s,s')$.  
> **username_1**: Please edit your question.  
> **username_2**: And "deadlocking" is equivalent to moving along a self-loop of the current vertex so that in the next time step, there is the possibility of leaving this vertex or is "deadlocking" equivalent to moving to a new sink vertex who's only outgoing edge is a self-loop and is taken with probability 1?  
> **username_1**: @Tyson: I did not realize the possibility of the former interpretation, but that is a good point.  
> **username_0**: No, deadlocking is equivalent to moving to a absorbing state from which the target state $t$ cannot be reached.  

---

## 0 answers

