Genericity, Randomness, and Polynomial-Time Approximations

DOI10.1137/S009753979630235XzbMath0915.68046OpenAlexW2017328704MaRDI QIDQ4210154

Yongge 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

zbMATH Keywords

computational complexityapproximationresource bounded genericityresource bounded randomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Limit theorems in probability theory (60F99)

Related Items

Resource bounded randomness and computational complexity

Cites Work

• Unnamed Item
• Diagonalizations over polynomial time computable sets
• Almost everywhere high nonuniform complexity
• Almost every set in exponential time is P-bi-immune
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Category and Measure in Complexity Classes
• Optimal Approximations and Polynomially Levelable Sets
• Completeness, Approximation and Density
• On optimal polynomial time approximations: P-levelability vs. δ-levelability
• E-complete sets do not have optimal polynomial time approximations