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 -