Skip to main content
SpringerLink
Log in

OnP-subset structures

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Given a setA, we investigate the lattice structure formed by those of its subsets that belong to the complexity classP, taken modulo finite variations and ordered by inclusion. We show that up to isomorphism, only three structures are possible for this lattice. IfA isP-immune, itsP-subset structure degenerates to the trivial one-element lattice. IfA is “almostP-immune” but notP-immune (for instance, ifA is inP), itsP-subset structure is isomorphic to the countable atomless Boolean latticeℬ. In all other cases theP-subset structure is isomorphic toℬ (ω), the weak countable power ofℬ. All natural intractable sets appear to fall in the third category. The results generalize to many other complexity classes, and similar characterizations hold for, e.g., the structures formed by recursive complexity cores.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Aspvall, M. F. Plass, and R. E. Tarjan. A linear time algorithm for testing the truth of certain quantified Boolean formulas.Inform. Process. Lett.,8 (1979), 121–123.

    Google Scholar 

  2. J. L. Balcázar. Separating, strongly separating, and collapsing complexity classes.Proc. 11th Symp. on Mathematical Foundations of Computer Science (1984), Lecture Notes in Computer Science, Vol. 176. Springer-Verlag, Berlin, 1984, pp. 1–16.

    Google Scholar 

  3. J. L. Balcázar and U. Schöning. Bi-immune sets for complexity classes.Math. Systems Theory,18 (1985), 1–10.

    Google Scholar 

  4. C. H. Bennett and J. Gill. Relative to a random oracleA, P A ≠NP A ≠ co-NP A with probability 1.SIAM J. Comput.,10 (1981), 96–113.

    Google Scholar 

  5. L. Berman. On the structure of complete sets: almost everywhere complexity and infinitely often speedup.Proc. 17th Ann. IEEE Symp. on Foundations of Computer Science (1976), 76–80.

  6. L. Berman and J. Hartmanis. On isomorphism and density ofNP and other complete sets.SIAM J. Comput.,6 (1977), 305–322.

    Google Scholar 

  7. S. Breidbart. On splitting recursive sets.J. Comput. System Sci.,17 (1978), 56–64.

    Google Scholar 

  8. S. A. Cook. The complexity of theorem-proving procedures.Proc. 3rd Ann. ACM Symp. on Theory of Computing (1971), 151–158.

  9. P. Flajolet and J. M. Steyaert. On sets having only hard subsets.Proc. 2nd Internat. Colloq. on Automata, Languages, and Programming (1974), Lecture Notes in Computer Science, Vol. 14. Springer-Verlag, Berlin, 1974, pp. 446–457.

    Google Scholar 

  10. J. G. Geske, D. T. Huynh, and A. L. Selman. A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees.Proc. 4th Symp. on Theoretical Aspects of Computer Science (1987), Lecture Notes in Computer Science, Vol. 247. Springer-Verlag, Berlin, 1987, pp. 125–135.

    Google Scholar 

  11. G. Grätzer.Lattice Theory. Freeman, San Francisco, 1971.

    Google Scholar 

  12. L. Henschen and L. Wos. Unit refutations and Horn sets.J. Assoc. Comput. Mach.,21 (1974), 590–605.

    Google Scholar 

  13. S. Homer and W. Maass. Oracle dependent properties of the lattice ofNP sets.Theoret. Comput. Sci.,24 (1983), 279–289.

    Google Scholar 

  14. J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass., 1979.

    Google Scholar 

  15. K. Ko and D. Moore. Completeness, approximation and density.SIAM J. Comput.,10 (1981), 787–796.

    Google Scholar 

  16. N. Lynch. On reducibility to complex or sparse sets.J. Assoc. Comput. Mach.,22 (1975), 341–345.

    Google Scholar 

  17. A. R. Meyer and M. S. Paterson. With what frequency are apparently intractable problems difficult? Report LCS/TM-126, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1979.

    Google Scholar 

  18. P. Orponen. A classification of complexity core lattices.Theoret. Comput. Sci.,47 (1986), 121–130.

    Google Scholar 

  19. P. Orponen, D. A. Russo, and U. Schöning. Optimal approximations and polynomially levelable sets.SIAM J. Comput.,15 (1986), 399–408.

    Google Scholar 

  20. P. Orponen and U. Schöning. The density and complexity of polynomial cores for intractable sets.Inform. and Control,70 (1986), 54–68.

    Google Scholar 

  21. H. Rogers, Jr.Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

    Google Scholar 

  22. U. Schöning. OnNP-decomposable sets.SIGACT News,14(1) (1982), 18–20.

    Google Scholar 

  23. U. Schöning and R. V. Book. Immunity, relativizations and nondeterminism.SIAM J. Comput.,13 (1984), 329–337.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California at Santa Barbara, 93106, Santa Barbara, CA, USA

    David A. Russo

  2. Department of Computer Science, University of Helsinki, SF-00250, Helsinki, Finland

    Pekka Orponen

Authors
  1. David A. Russo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pekka Orponen
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by the Emil Aaltonen Foundation, the Academy of Finland, and the National Science Foundation under Grant No. MCS83-14272. Part of the work was carried out while the second author was visiting the Department of Mathematics, University of California at Santa Barbara.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Russo, D.A., Orponen, P. OnP-subset structures. Math. Systems Theory 20, 129–136 (1987). https://doi.org/10.1007/BF01692061

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01692061

Keywords

Search

Navigation