Polynomial time samplable distributions
From MaRDI portal
Publication:1578504
DOI10.1006/jcom.1999.0523zbMath0949.68070OpenAlexW1964170686MaRDI QIDQ1578504
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
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