Almost complete sets.
DOI10.1016/S0304-3975(03)00262-7zbMath1048.03032OpenAlexW2019482663MaRDI QIDQ1426448
Sebastiaan A. Terwijn, Wolfgang Merkle, Jan Reimann, Ambos-Spies, Klaus
Publication date: 14 March 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00262-7
resource-bounded measureweak completenessalmost completeness1-tt-reductionslength-increasing one-one reductionsmany-one reductionsresource-bounded reducibilities
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (1)
Cites Work
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- A comparison of polynomial time completeness notions
- Almost everywhere high nonuniform complexity
- On 1-truth-table-hard languages
- Almost every set in exponential time is P-bi-immune
- Genericity and measure for exponential time
- Resource bounded randomness and weakly complete problems
- Weakly complete problems are not rare
- A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
- The Complexity and Distribution of Hard Problems
- Weakly Hard Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Almost complete sets.
