Genericity, Randomness, and Polynomial-Time Approximations
From MaRDI portal
Publication:4210154
DOI10.1137/S009753979630235XzbMath0915.68046OpenAlexW2017328704MaRDI QIDQ4210154
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
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
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