Genericity, Randomness, and Polynomial-Time Approximations

DOI10.1137/S009753979630235XMaRDI QIDQ4210154zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexityapproximationresource bounded genericityresource bounded randomness

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• Category and Measure in Complexity Classes
• Completeness, Approximation and Density
• Diagonalizations over polynomial time computable sets
• E-complete sets do not have optimal polynomial time approximations
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
• Optimal Approximations and Polynomially Levelable Sets

Cited in

(4)

• E-complete sets do not have optimal polynomial time approximations
• A nonapproximability result for finite function generation
• Resource bounded randomness and computational complexity
• On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability

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)