Almost complete sets.

DOI10.1016/S0304-3975(03)00262-7zbMath1048.03032MaRDI QIDQ1426448

Ambos-Spies, Klaus, Sebastiaan A. Terwijn, Wolfgang Merkle, Jan Reimann

Publication date: 14 March 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

resource-bounded measure; weak completeness; almost completeness; 1-tt-reductions; length-increasing one-one reductions; many-one reductions; resource-bounded reducibilities

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D30: Other degrees and reducibilities in computability and recursion theory

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