Skip to main content
SpringerLink
Log in

Nonlevelable sets and immune sets in the accepting density hierarchy inNP

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

The complexity theoretic concept of levelability is introduced to the accepting density hierarchy inNP. A setA inNP islevelable with respect to densityu(n) if for every polynomial-time nondeterministic Turing machine (NTM)M that acceptsA there is a better NTMM′ forA that improves the accepting density ofM infinitely often from the density belowu(n) tou(n). We investigate the structural properties of nonlevelable sets inNP. A nonlevelable set must have a maximal complexity core, and its maximal cores must have relatively low complexity. Most naturalNP-complete sets are paddable and hence levelable with respect to the two lowest levels in the accepting density hierarchy. A relativized accepting density hierarchy is constructed to demonstrate the possibility of the existence of nonlevelable sets at each level of the hierarchy.

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. Adleman, L., Two theorems on random polynomial time,Proc. 19th IEEE Symp. on Foundations of Computer Science (1978), 75–83.

  2. Angluin, D., On counting problems and the polynomial-time hierarchy,Theoret. Comput. Sci. 12 (1980), 161–173.

    Google Scholar 

  3. Balcazar, J. and D. Russo, Immunity and simplicity in relativizations of probabilistic complexity classes, preprint.

  4. Balcazar, J. and U. Schöning, Bi-immune sets for complexity classes,Math. Systems Theory, (to appear).

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

    Google Scholar 

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

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

    Google Scholar 

  8. Blum M. and I. Marques, On complexity properties of recursively enumerable sets,J. Symbol. Logic 38 (1973), 579–593.

    Google Scholar 

  9. Cook, S., A hierarchy for nondeterministic time complexity,J. Comput. System Sci. 7 (1973) 343–353.

    Google Scholar 

  10. Even, S., A. Selman and Y. Yacobi, Hard-core theorems for complexity classes,J. Assoc. Comput. Mach. (1985), to appear.

  11. Garey, M. and D. Johnson,Computers and Intractability, W. H. Freeman, San Francisco, 1979.

    Google Scholar 

  12. Gill, J., Computational complexity of probabilistic Turing machines,SIAM J. Comput. 6 (1977), 675–695.

    Google Scholar 

  13. Hartmanis, J., Generalized Kolmogorov complexity and the structure of feasible computations,Proc. 24th IEEE Symp. on Foundation of Computer Science (1983) 439–445.

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

    Google Scholar 

  15. Karp, R. and R. Lipton, Some connections between nonuniform and uniform complexity classes,Proc. 12th ACM Symp. Theory of Comput. (1980), 302–309.

  16. Kintala, C. and P. Fischer, Refining nondeterminism in relativized polynomial time bounded computations,SIAM J. Comput. 9 (1980) 46–53.

    Google Scholar 

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

    Google Scholar 

  18. Ko, K. and U. Schöning, On circuit-size complexity and the low hierarchy inNP, SIAM J. Comput. (1985), 41–51.

  19. Lautemann, C., BPP and the polynomial hierarchy,Inform. Proc. Letters 17 (1983), 215–217.

    Google Scholar 

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

    Google Scholar 

  21. Moran, S., On the accepting density hierarchy inNP, SIAM J. Comput. 11 (1982) 344–349.

    Google Scholar 

  22. Orponen, P., A classification of complexity core lattices, preprint.

  23. Orponen, P., D. Russo and U. Schöning, Optimal approximations and polynomially levelable sets, SIAM J. Comput., to appear.

  24. Orponen, P. and U. Schöning, The structure of polynomial complexity cores,Proc. 11th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 176 (1984), 452–458.

    Google Scholar 

  25. Papadimitriou, C. H. and M. Yanakakis, The complexity of facets,Proc. 14th ACM Symp. on Theory of Computing (1982), 255–260.

  26. Rabin, M., Probabilistic algorithms, inAlgorithm and Complexity, J. F. Traub, ed., Academic Press (1976) 21–39.

  27. Rackoff, C., Relativized questions involving probabilistic algorithms,J. Assoc. Comput. Mach. 29 (1982), 261–268.

    Google Scholar 

  28. Schöning, U., A low and a high hierarchy withinNP, J. Comput. System Sci. 27 (1983) 14–28.

    Google Scholar 

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

    Google Scholar 

  30. Seiferas, J., M. Fischer and A. Meyer, Separating nondeterministic time complexity classes,J. Assoc. Comput. Mach. 25 (1978) 146–167.

    Google Scholar 

  31. Sipser, M., A complexity theoretic approach to randomness,Proc. 15th ACM Symp. on Theory of Computing (1983) 330–335.

  32. Soare, R., Computational complexity, speedable and levelable sets,J. Symbolic Logic, 42 (1977) 545–563.

    Google Scholar 

  33. Stockmeyer, L., The polynomial time hierarchy.Theoret. Comput. Sci. 3 (1976) 1–22.

    Google Scholar 

  34. Valiant, L. G., The complexity of computing the permanent,Theoret. Comput. Sci. 8 (1979), 189–201.

    Google Scholar 

  35. Valiant, L. G., The complexity of reliability and enumeration problems,SIAM J. Comput. 8 (1979), 410–421.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Houston, 77004, Houston, Texas, USA

    Ker-I Ko

Authors
  1. Ker-I Ko
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by the National Science Foundation under Grants MCS-8103479 and MCS-8103479A01.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ko, KI. Nonlevelable sets and immune sets in the accepting density hierarchy inNP . Math. Systems Theory 18, 189–205 (1985). https://doi.org/10.1007/BF01699469

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation