Almost complete sets. (Q1426448): Difference between revisions

The authors consider the class \({\mathbf E}\) of sets being computable in (linear) exponential time. They define the concept of almost completeness for the class \({\mathbf E}\) under some given reducibility if the class of languages in \({\mathbf E}\) that do not reduce to this set has measure 0 in \({\mathbf E}\), in the sense of Lutz's resource-bounded measure theory, based on polynomial-time computable martingales. The main result states that there are sets in \({\mathbf E}\) being almost complete but not complete under polynomial-time many-one reductions.