The Markov Reachability Problem We are interested in decision problems for Markov chains and in particular, the Markov Reachability Problem. Given a stochastic matrix $K\in\mathbb{Q}^{d\times d}$ and positive $r\in\mathbb{Q}$, determine whether there exist an $n\in\mathbb{N}$ such that $K^n(1,2)=r$.
