Abstract
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.
Supported by Marie Curie Fellowship ERB-FMBI-CT98-3248.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP. In: Proceedings of the 35th Annual IEEE Symposium an Foundations of Computer Science, p.867–818, IEEE Computer Society Press, 1994.
K. Ambos-Spies, S. Lempp, and G. Mainhardt. Randomness vs. completeness: on the diagonalization strength of resource bounded random sets. In: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, p. 465–473, Lecture Notes in Computer Science, Vol. 1450, Springer, 1998.
K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In: A. Sorbi (ed.), Complexity, logic, and recursion theory, p.1–47. Dekker, New York, 1997.
K. Ambos-Spies, E. Mayordomo and X. Zheng. A comparison of weak completeness notions. In: Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.171–178, IEEE Computer Society Press, 1996.
K. Ambos-Spies, H.-C. Neis and S. A. Terwijn. Genericity and measure for exponential time. Theoretical Computer Science, 168:3–19, 1996.
K. Ambos-Spies, S. A. Terwijn and X. Zheng. Resource bounded randomness and weakly complete problems. Theoretical Computer Science, 172:195–207, 1997.
J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity, volume I. Springer-Verlag, 1995.
L. Berman. Polynomial reducibilities and complete sets. Ph.D. thesis, Cornell University, 1977.
H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, M. Strauss. A generalization of resource bounded measure, with application to the BPP vs. EXP problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.161–171, Lecture Notes in Computer Science, Vol. 1373, Springer, 1998.
S. Homer, S. Kurtz and J. Royer. On 1-truth-table-hard languages. Theoretical Computer Science, 115:383–389, 1993.
D. W. Juedes. Weakly complete problems are not rare. Computational Complexity, 5:267–283, 1995.
D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24:279–295, 1995.
D. W. Juedes and J. H. Lutz. Weak completeness in E and E 2. Theoretical Computer Science, 143:149–158, 1995.
J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220–258, 1992.
J. H. Lutz. Weakly hard problems. SIAM Journal on Computing 24:1170–1189, 1995.
J. H. Lutz. The quantitative structure of exponential time. In: Hemaspaandra, Lane A. (ed.) et al., Complexity theory retrospective II, p.225–260. Springer, New York, 1997.
E. Mayordomo. Almost every set in exponential time is P-bi-immune. Theoretical Computer Science, 136:487–506, 1994.
K. Regan, D. Sivakumar and J.-Y. Cai. Pseudorandom generators, measure theory and natural proofs. In: Proceedings of the 36th Annual IEEE Symposium an Foundations of Computer Science, p.171–178, IEEE Computer Society Press, 1995.
K. Regan, D. Sivakumar. Improved Resource-Bounded Borel-Cantelli and Stochasticity Theorems. Technical Report UBCS-TR 95-08, Department of Computer Science, State University of New York at Buffalo, 1995.
O. Watanabe. A comparison of polynomial time completeness notions. Theoretical Computer Science, 54:249–265, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ambos-Spies, K., Merkle, W., Reimann, J., Terwijn, S.A. (2000). Almost Complete Sets. In: Reichel, H., Tison, S. (eds) STACS 2000. STACS 2000. Lecture Notes in Computer Science, vol 1770. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46541-3_35
Download citation
DOI: https://doi.org/10.1007/3-540-46541-3_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67141-1
Online ISBN: 978-3-540-46541-6
eBook Packages: Springer Book Archive