TY - GEN
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: ambos@math.uni-heidelberg.de (K. Ambos-Spies), merkle@math.uni-heidelberg.de (W. Merkle), reimann@math.uni-heidelberg.de (J. Reimann),terwijn@cs.vu.nl (S.A. Terwijn). 1Supported by a Marie Curie Fellowship of the European Union under grant ERB-FMBI-CT98-3248.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - We show that there is a set which 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 A in a complexity class C is almost complete for C under some reducibility r if the class of the problems in C which do not r-reduce to A 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 one-one length-increasing 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 which 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 A in a complexity class C is almost complete for C under some reducibility r if the class of the problems in C which do not r-reduce to A 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 one-one length-increasing 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=84944081286&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84944081286&partnerID=8YFLogxK
U2 - 10.1007/3-540-46541-3_35
DO - 10.1007/3-540-46541-3_35
M3 - Conference contribution
AN - SCOPUS:84944081286
SN - 9783540671411
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 419
EP - 430
BT - STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings
A2 - Reichel, Horst
A2 - Tison, Sophie
PB - Springer Verlag
T2 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000
Y2 - 17 February 2000 through 19 February 2000
ER -