Advertisement
Published in:
2020 | OriginalPaper | Chapter
Promise Problems on Probability Distributions
Authors : Jan-Hendrik Lorenz, Uwe Schöning
Published in: Complexity and Approximation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider probability distributions which are associated with the running time of probabilistic algorithms, given for algorithmic processing in symbolic form. The considered decision (also counting) problems deal with the question whether a complete restart of the underlying probabilistic algorithm after some number of steps t gives an advantage. Since deciding whether a given symbolic formula indeed represents a probability distribution (either as probability mass function or as cumulative distribution function) is itself a difficult problem to decide, we discuss the issue in terms of promise problems.