# On the Hardness of Almost-Sure Termination

arXiv: https://arxiv.org/abs/1506.01930 · HTML: https://mlsanity.com/paper/1506.01930/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2015.

## Built on by (most cited first, 2 of 2)

- [Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving](https://mlsanity.com/paper/2303.09692/) (2023)
- [Automating the Refinement of Reinforcement Learning Specifications](https://mlsanity.com/paper/2512.01047/) (2025)

## Abstract (arXiv)

This paper considers the computational hardness of computing expected outcomes and deciding (universal) (positive) almost-sure termination of probabilistic programs. It is shown that computing lower and upper bounds of expected outcomes is Sigma10- and Sigma20-complete, respectively. Deciding (universal) almost-sure termination as well as deciding whether the expected outcome of a program equals a given rational value is shown to be Pi02-complete. Finally, it is shown that deciding (universal) positive almost-sure termination is Sigma20-complete (Pi30-complete).