Almost complete sets
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 I 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). (C) 2003 Elsevier B.V. All rights reserved.
almost completeness completeness resource-bounded measure length-increasing one-one reductions weak completeness resource-bounded reducibilities many-one reductions 1-tt-reductions