Completeness and weak completeness under polynomial-size circuits | SpringerLink
Skip to main content
Springer Nature Link
Log in

Completeness and weak completeness under polynomial-size circuits

  • Conference paper
  • First Online:
STACS 95 (STACS 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 900))

Included in the following conference series:

Abstract

This paper investigates the distribution and nonuniform complexity of problems that are complete or weakly complete for ESPACE under nonuniform many-one reductions that are computed by polynomial-size circuits (P/Poly-many-one reductions). Every weakly P/Poly-many-one-complete problem is shown to have a dense, exponential, nonuniform complexity core. An exponential lower bound on the space-bounded Kolmogorov complexities of weakly P/Poly-Turing-complete problems is established. More importantly, the P/Poly-many-one-complete problems are shown to be unusually simple elements of ESPACE, in the sense that they obey nontrivial upper bounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE. More generally, a Small Span Theorem for P/Poly-many-one reducibility in ESPACE is proven and used to show that every P/Poly-many-one degree -including the complete degree — has measure 0 in ESPACE. (In contrast, almost every element of ESPACE is weakly P-many-one complete.) All upper and lower bounds are shown to be tight.

This work was supported in part by National Science Foundation Grant CCR-9157382, with matching funds from Rockwell International, Microware Systems Corporation, and Amoco Foundation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Allender and R. Rubinstein. P-printable sets. SIAM Journal on Computing, 17:1193–1202, 1988.

    Google Scholar 

  2. E. W. Allender. Some consequences of the existence of pseudorandom generators. Journal of Computer and System Sciences, 39:101–124, 1989.

    Google Scholar 

  3. E. W. Allender and O. Watanabe. Kolmogorov complexity and degrees of tally sets. Information and Computation, 86:160–178, 1990.

    Google Scholar 

  4. K. Ambos-Spies, S. A. Terwijn, and Zheng Xizhong. Resource bounded randomness and weakly complete problems. In Proceedings of the Fifth Annual International Symposium on Algorithms and Computation, pages 369–377. Springer-Verlag, 1994.

    Google Scholar 

  5. J. L. Balcázar and R. V. Book. Sets with small generalized Kolmogorov complexity. Acta Informatica, 23:679–688, 1986.

    Google Scholar 

  6. J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I. Springer-Verlag, Berlin, 1988.

    Google Scholar 

  7. J. L. Balcázar and U. Schöning. Bi-immune sets for complexity classes. Mathematical Systems Theory, 18:1–10, 1985.

    Google Scholar 

  8. R. Book and D.-Z. Du. The existence and density of generalized complexity cores. Journal of the ACM, 34:718–730, 1987.

    Google Scholar 

  9. R. Book, D.-Z Du, and D. Russo. On polynomial and generalized complexity cores. In Proceedings of the Third Structure in Complexity Theory Conference, pages 236–250, 1988.

    Google Scholar 

  10. G. J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the Association for Computing Machinery, 13:547–569, 1966.

    Google Scholar 

  11. D.-Z. Du. Generalized complexity cores and levelability of intractable sets. Ph.D. thesis, University of California, Santa Barbara, 1985.

    Google Scholar 

  12. D.-Z. Du and R. Book. On inefficient special cases of NP-complete problems. Theoretical Computer Science, 63:239–252, 1989.

    Google Scholar 

  13. S. Even, A. Selman, and Y. Yacobi. Hard core theorems for complexity classes. Journal of the ACM, 35:205–217, 1985.

    Google Scholar 

  14. J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proceedings of the 24th IEEE Symposium on the Foundations of Computer Science, pages 439–445, 1983.

    Google Scholar 

  15. J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities. Theoretical Computer Science, 34:17–32, 1984.

    Google Scholar 

  16. D. T. Huynh. Resource-bounded Kolmogorov complexity of hard languages, Structure in Complexity Theory, pages 184–195. Springer-Verlag, Berlin, 1986.

    Google Scholar 

  17. D. T. Huynh. On solving hard problems by polynomial-size circuits. Information Processing Letters, 24:171–176, 1987.

    Google Scholar 

  18. D. W. Juedes. The Complexity and Distribution of Computationally Useful Problems. Ph.D. thesis, Iowa State University, 1994.

    Google Scholar 

  19. D. W. Juedes. Weakly complete problems are not rare. submitted, 1994.

    Google Scholar 

  20. D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24, 1995. to appear.

    Google Scholar 

  21. D. W. Juedes and J. H. Lutz. Weak completeness in E and E2. Theoretical Computer Science, 1995. to appear.

    Google Scholar 

  22. R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55:40–56, 1982.

    Google Scholar 

  23. R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–104. Plenum Press, New York, 1972.

    Google Scholar 

  24. R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 302–309, 1980.

    Google Scholar 

  25. K. Ko. On the notion of infinite pseudorandom sequences. Theoretical Computer Science, 48:9–33, 1986.

    Google Scholar 

  26. A. N. Kolmogorov. Three approaches to the quantitative definition of ‘information'. Problems of Information Transmission, 1:1–7, 1965.

    Google Scholar 

  27. L. A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61:15–37, 1984.

    Google Scholar 

  28. L. Longpré. Resource Bounded Kolmogorov Complexity, a Link Between Computational Complexity and Information Theory. Ph.D. thesis, Cornell University, 1986. Technical Report TR-86-776.

    Google Scholar 

  29. J. H. Lutz. Resource-bounded measure. in preparation.

    Google Scholar 

  30. J. H. Lutz. Weakly hard problems. SIAM Journal on Computing, to appear. See also Proceedings of the Ninth Structure in Complexity Theory Conference, 1994, pp. 146–161. IEEE Computer Society Press.

    Google Scholar 

  31. J. H. Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19:1100–1131, 1990.

    Google Scholar 

  32. J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220–258, 1992.

    Google Scholar 

  33. J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, to appear. See also Proceedings of the Eleventh Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 1994, pp. 415–426.

    Google Scholar 

  34. J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, 23:762–779, 1994.

    Google Scholar 

  35. N. Lynch. On reducibility to complex or sparse sets. Journal of the ACM, 22:341–345, 1975.

    Google Scholar 

  36. P. Martin-Löf. Complexity oscillations in infinite binary sequences. Zeitschrift für Wahrscheinlichkeitstheory und Verwandte Gebiete, 19:225–230, 1971.

    Google Scholar 

  37. E. Mayordomo. Contributions to the study of resource-bounded measure. Ph.D. thesis, Universitat Politècnica de Catalunya, 1994.

    Google Scholar 

  38. P. Orponen. A classification of complexity core lattices. Theoretical Computer Science, 70:121–130, 1986.

    Google Scholar 

  39. P. Orponen and U. Schöning. The density and complexity of polynomial cores for intractable sets. Information and Control, 70:54–68, 1986.

    Google Scholar 

  40. D. A. Russo and P. Orponen. On P-subset structures. Mathematical Systems Theory, 20:129–136, 1987.

    Google Scholar 

  41. M. Sipser. A complexity-theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330–335, 1983.

    Google Scholar 

  42. S. Skyum and L. G. Valiant. A complexity theory based on boolean algebra. Journal of the ACM, 32:484–502, 1985.

    Google Scholar 

  43. R. J. Solomonoff. A formal theory of inductive inference. Information and Control, 7:1–22, 224–254, 1964.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Ohio University, 45701, Athens, Ohio, USA

    David W. Juedes

  2. Department of Computer Science, Iowa State University, 50011, Ames, Iowa, USA

    Jack H. Lutz

Authors
  1. David W. Juedes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jack H. Lutz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Ernst W. Mayr Claude Puech

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Juedes, D.W., Lutz, J.H. (1995). Completeness and weak completeness under polynomial-size circuits. In: Mayr, E.W., Puech, C. (eds) STACS 95. STACS 1995. Lecture Notes in Computer Science, vol 900. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59042-0_59

Download citation

  • DOI: https://doi.org/10.1007/3-540-59042-0_59

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-59042-2

  • Online ISBN: 978-3-540-49175-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation