Almost complete sets

✍ Scribed by Klaus Ambos-Spies; Wolfgang Merkle; Jan Reimann; Sebastiaan A. Terwijn

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 353 KB
• Volume: 306
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00262-7

✦ Synopsis

We show that there is a set that is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class E of sets computable in deterministic time 2 lin . Here a set in a complexity class C is almost complete for C under some given reducibility if the class of the problems in C that do not reduce to this set has measure 0 in C in the sense of Lutz's resource-bounded measure theory. We also show that the almost complete sets for E under polynomial time-bounded length-increasing one-one reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for E. Moreover, we obtain similar results for the class EXP of sets computable in deterministic time 2 poly .