Nonlevelable sets and immune sets in the accepting density hierarchy in NP. (English) Zbl 0586.68043

Ko, Ker-I

Math. Syst. Theory 18, 189-205 (1985).

The author studies the concept of levelability (investigated earlier at the recursive level) at the level of the accepting density hierarchy in NP. A set A in NP is levelable with respect to a density function u [ND(u(n))-levelable] if for every polynomial-time nondeterministic Turing machine (NTM) M that accepts A there is a NTM M’ accepting A and such that for infinitely many strings x in A, probability of the acceptance of x by M \(< u(| x|) \leq\) probability of the acceptance of x by M’.
The paper contains several results establishing an interesting characterization of nonlevelable sets in NP in terms of their maximal complexity cores, a relation between paddability and levelability at the two lowest levels in the accepting density hierarchy. Finally, the relation between the ND(u(n))-levelable and the ND(u(n))-immune sets in the relativized ND-hierarchy is studied.

Reviewer: M.Chytil

MSC:

68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

time complexity; levelability; levelable with respect to a density function; complexity cores; paddability

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. · Zbl 0499.68020 · doi:10.1016/0304-3975(80)90027-4
[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 P A coNP A with probability 1,SIAM. J. Comput. 10 (1981), 96–113. · Zbl 0454.68030 · doi:10.1137/0210008
[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. · Zbl 0356.68059 · doi:10.1137/0206023
[8]	Blum M. and I. Marques, On complexity properties of recursively enumerable sets,J. Symbol. Logic 38 (1973), 579–593. · Zbl 0335.02024 · doi:10.2307/2271984
[9]	Cook, S., A hierarchy for nondeterministic time complexity,J. Comput. System Sci. 7 (1973) 343–353. · Zbl 0278.68042 · doi:10.1016/S0022-0000(73)80028-5
[10]	Even, S., A. Selman and Y. Yacobi, Hard-core theorems for complexity classes,J. Assoc. Comput. Mach. (1985), to appear. · Zbl 0632.68047
[11]	Garey, M. and D. Johnson,Computers and Intractability, W. H. Freeman, San Francisco, 1979.
[12]	Gill, J., Computational complexity of probabilistic Turing machines,SIAM J. Comput. 6 (1977), 675–695. · Zbl 0366.02024 · doi:10.1137/0206049
[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. · Zbl 0543.03024 · doi:10.1016/0304-3975(83)90003-8
[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. · Zbl 0447.68044 · doi:10.1137/0209003
[17]	Ko, K. and D. Moore, Completeness, approximation and density,SIAM J. Comput. 10 (1981), 787–796. · Zbl 0468.68051 · doi:10.1137/0210061
[18]	Ko, K. and U. Schöning, On circuit-size complexity and the low hierarchy inNP, SIAM J. Comput. (1985), 41–51. · Zbl 0562.68033
[19]	Lautemann, C., BPP and the polynomial hierarchy,Inform. Proc. Letters 17 (1983), 215–217. · Zbl 0515.68042 · doi:10.1016/0020-0190(83)90044-3
[20]	Lynch, N., On reducibility to complex or sparse sets,J. Assoc. Comput. Mach. 22 (1975) 341–345. · Zbl 0311.68037
[21]	Moran, S., On the accepting density hierarchy inNP, SIAM J. Comput. 11 (1982) 344–349. · Zbl 0478.68038 · doi:10.1137/0211026
[22]	Orponen, P., A classification of complexity core lattices, preprint. · Zbl 0638.68033
[23]	Orponen, P., D. Russo and U. Schöning, Optimal approximations and polynomially levelable sets, SIAM J. Comput., to appear. · Zbl 0644.68054
[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. · Zbl 0556.68014
[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. · Zbl 0477.68037
[28]	Schöning, U., A low and a high hierarchy withinNP, J. Comput. System Sci. 27 (1983) 14–28. · Zbl 0515.68046 · doi:10.1016/0022-0000(83)90027-2
[29]	Schöning, U. and R. Book, Immunity, relativizations and nondeterminism,SIAM J. Comput. 13 (1984), 329–337. · Zbl 0558.68039 · doi:10.1137/0213023
[30]	Seiferas, J., M. Fischer and A. Meyer, Separating nondeterministic time complexity classes,J. Assoc. Comput. Mach. 25 (1978) 146–167. · Zbl 0366.68038
[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. · Zbl 0401.68020 · doi:10.2307/2271876
[33]	Stockmeyer, L., The polynomial time hierarchy.Theoret. Comput. Sci. 3 (1976) 1–22. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[34]	Valiant, L. G., The complexity of computing the permanent,Theoret. Comput. Sci. 8 (1979), 189–201. · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6
[35]	Valiant, L. G., The complexity of reliability and enumeration problems,SIAM J. Comput. 8 (1979), 410–421. · Zbl 0419.68082 · doi:10.1137/0208032