Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the probability of eventually reaching $F$ from $q_0$ greater than (or equal to) $\frac{1}{2}$?
Complexity of reachability in Markov Chains
cc.complexity theory;time complexity;markov chains