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

zbMATH Keywords

resource-bounded measureweak completenessalmost completeness1-tt-reductionslength-increasing one-one reductionsmany-one reductionsresource-bounded reducibilities

Mathematics Subject Classification ID

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

A note on measuring in P

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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