Analyzing Expected Outcomes and Almost-Sure Termination of Probabilistic Programs is Hard

Benjamin Lucien Kaminski, Joost-Pieter Katoen

This paper considers the computational hardness of computing expected outcomes and deciding almost-sure termination of probabilistic programs. We show that deciding almost-sure ter…