Promise problems on probability distributions

DOI10.1007/978-3-030-41672-0_5MaRDI QIDQ3297824zbMATH OpenOpenAlexFDO

Authors Jan-Hendrik Lorenz, Uwe Schöning

Publication date 20 July 2020

Published in Complexity and Approximation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-41672-0_5

zbMATH Keywords

probability distributionspromise problemsrestart strategies

Mathematics Subject Classification ID

Distribution theory (60E99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

Recommendations

• Promise problems complete for complexity classes
• Stochastic Algorithms: Foundations and Applications
• A probabilistic anytime algorithm for the halting problem
• A statistical anytime algorithm for the halting problem
• A variation on the zero-one law

Cites work

• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• On the complexity of restarting
• Optimal speedup of Las Vegas algorithms
• PP is as Hard as the Polynomial-Time Hierarchy
• Promise problems complete for complexity classes
• The complexity of promise problems with applications to public-key cryptography

Cited in

(1)

• Restart strategies in a continuous setting

This page was built for publication: Promise problems on probability distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297824)