Almost complete sets
It is shown that there is a set which is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class \({\mathbf E}\) of sets computable in deterministic time \(2^{\text{lin}}\). A set \(A\) in a complexity class \({\mathbf C}\) is almost complete for \({\mathbf C}\) under some reducibility \(r\) if the class of the problems in \({\mathbf C}\) which do not \(r\)-reduce to \(A\) has measure 0 in \({\mathbf C}\) in the sense of resource-bounded measure theory. Furthermore, it is shown that the almost complete sets for \({\mathbf E}\) under polynomial-time bounded one-one length-increasing reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for \({\mathbf E}\). Moreover, similar results for the class \({\mathbf {EXP}}\) of sets computable in deterministic time \(2^{\text{poly}}\) are obtained. For the entire collection see [Zbl 0933.00044].
- Almost complete sets.
- Hard sets are hard to find
- Almost semirecursive sets
- scientific article; zbMATH DE number 4010508 (Why is no real title available?)
- scientific article; zbMATH DE number 1335891 (Why is no real title available?)
- Completeness and weak completeness under polynomial-size circuits
- Complete sets and closeness to complexity classes
- Constructions of complete sets
This page was built for publication: Almost complete sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501552)
