Almost complete sets
โ
Klaus Ambos-Spies; Wolfgang Merkle; Jan Reimann; Sebastiaan A. Terwijn
๐
Article
๐
2003
๐
Elsevier Science
๐
English
โ 353 KB
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 2 lin . Here a set in a complexity class C is almost complete for C under some given reducibility if the class of the problems