Genericity, Randomness, and Polynomial-Time Approximations
DOI10.1137/S009753979630235XzbMATH Open0915.68046OpenAlexW2017328704MaRDI QIDQ4210154FDOQ4210154
Authors: Y. Wang 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753979630235x
Recommendations
- scientific article; zbMATH DE number 1492083
- On the interplay between effective notions of randomness and genericity
- scientific article; zbMATH DE number 1008512
- Genericity and randomness over feasible probability measures
- scientific article; zbMATH DE number 3995648
- A Note on Randomized Polynomial Time
- Resource-bounded balanced genericity, stochasticity and weak randomness
- Higher randomness and genericity
- Genericity and randomness with ITTMs
- scientific article; zbMATH DE number 1566488
Analysis of algorithms and problem complexity (68Q25) Limit theorems in probability theory (60F99) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Almost everywhere high nonuniform complexity
- Title not available (Why is that?)
- Category and Measure in Complexity Classes
- Diagonalizations over polynomial time computable sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Completeness, Approximation and Density
- Almost every set in exponential time is P-bi-immune
- Optimal Approximations and Polynomially Levelable Sets
- On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
- E-complete sets do not have optimal polynomial time approximations
Cited In (4)
This page was built for publication: Genericity, Randomness, and Polynomial-Time Approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210154)
