




Publications  The Odds of Staying on Budget





Reference:
Christoph Haase and Stefan Kiefer. The odds of staying on budget. Technical report, arXiv.org, 2015. Available at http://arxiv.org/abs/1409.8228.
Abstract:
Given Markov chains and Markov decision processes (MDPs) whose transitions are labelled with nonnegative integer costs, we study the computational complexity of deciding whether the probability of paths whose accumulated cost satisfies a Boolean combination of inequalities exceeds a given threshold. For acyclic Markov chains, we show that this problem is PPcomplete, whereas it is hard for the PosSLP problem and in PSPACE for general Markov chains. Moreover, for acyclic and general MDPs, we prove PSPACE and EXPcompleteness, respectively. Our results have direct implications on the complexity of computing reward quantiles in succinctly represented stochastic systems.
Suggested BibTeX entry:
@techreport{15HKICALPTR,
author = {Christoph Haase and Stefan Kiefer},
institution = {arXiv.org},
note = {Available at http://arxiv.org/abs/1409.8228},
title = {The Odds of Staying on Budget},
year = {2015}
}




