Resource bounded randomness and weakly complete problems
From MaRDI portal
Publication:1392022
DOI10.1016/S0304-3975(95)00260-XzbMath0912.68069OpenAlexW2169825513MaRDI QIDQ1392022
Sebastiaan A. Terwijn, Zheng, Xizhong, Ambos-Spies, Klaus
Publication date: 23 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(95)00260-x
Related Items
Bi-immunity separates strong NP-completeness notions ⋮ Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ A thirty year old conjecture about promise problems ⋮ A note on measuring in P ⋮ Comparing reductions to NP-complete sets ⋮ Turing's unpublished algorithm for normal numbers ⋮ Functions that preserve p-randomness ⋮ A Theory of Bounded Inductive Rationality ⋮ Almost complete sets. ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Comparing nontriviality for E and EXP ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ A note on dimensions of polynomial size circuits ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ Genericity and randomness over feasible probability measures ⋮ Weak completeness notions for exponential time ⋮ Resource-bounded martingales and computable Dowd-type generic sets ⋮ Feasible analysis, randomness, and base invariance
Cites Work
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Diagonalizations over polynomial time computable sets
- Almost everywhere high nonuniform complexity
- Category and Measure in Complexity Classes
- The density and complexity of polynomial cores for intractable sets
- Measure, Stochasticity, and the Density of Hard Languages
- The Complexity and Distribution of Hard Problems
- Genericity and measure for exponential time
- The definition of random sequences
- Unnamed Item
- Unnamed Item
- Unnamed Item
