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

approximationcomputational complexityresource bounded genericityresource bounded randomness

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On optimal polynomial time approximations: p-levelability vs. -levelability
• Optimal Approximations and Polynomially Levelable Sets

Cited in

(6)

• Resource bounded randomness and computational complexity
• Randomness, stochasticity, and approximations
• A nonapproximability result for finite function generation
• On optimal polynomial time approximations: p-levelability vs. -levelability
• E-complete sets do not have optimal polynomial time approximations
• Computable one-way functions on the reals

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)