Back to Search
Start Over
On the Hardness of Almost-Sure Termination
- Publication Year :
- 2015
-
Abstract
- 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 $\Sigma_1^0$- and $\Sigma_2^0$-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 $\Pi^0_2$-complete. Finally, it is shown that deciding (universal) positive almost-sure termination is $\Sigma_2^0$-complete ($\Pi_3^0$-complete).<br />Comment: MFCS 2015. arXiv admin note: text overlap with arXiv:1410.7225
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1506.01930
- Document Type :
- Working Paper