Polynomial time samplable distributions

DOI10.1006/jcom.1999.0523zbMath0949.68070OpenAlexW1964170686MaRDI QIDQ1578504

Tomoyuki Yamakami

Publication date: 3 September 2000

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1999.0523

zbMATH Keywords

polynomial-time computable distributionspolynomial-time samplable distributions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity and structure
• Probabilistic quantifiers and games
• Some observations on the probabilistic algorithms and NP-hard problems
• Computational complexity of real functions
• Average case completeness
• On the theory of average case complexity
• Minimum-complexity pairing functions
• Some properties of sets tractable under every polynomial-time computable distribution
• On the NP-isomorphism problem with respect to random instances
• Structural average case complexity
• Randomizing Reductions of Search Problems
• Average Case Complete Problems
• The Complexity of Malign Measures