TY - JOUR
T1 - Almost complete sets
AU - Ambos-Spies, Klaus
AU - Merkle, Wolfgang
AU - Reimann, Jan
AU - Terwijn, Sebastiaan A.
N1 - Funding Information:
∗Corresponding author. Tel.: +49-6221-54-5409. E-mail addresses: [email protected] (K. Ambos-Spies), [email protected] (W. Merkle), [email protected] (J. Reimann),[email protected] (S.A. Terwijn). 1Supported by a Marie Curie Fellowship of the European Union under grant ERB-FMBI-CT98-3248.
PY - 2003/9/5
Y1 - 2003/9/5
N2 - 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 2lin. 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 2poly.
AB - 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 2lin. 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 2poly.
UR - http://www.scopus.com/inward/record.url?scp=0042508855&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0042508855&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(03)00262-7
DO - 10.1016/S0304-3975(03)00262-7
M3 - Article
AN - SCOPUS:0042508855
SN - 0304-3975
VL - 306
SP - 177
EP - 194
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -