×

zbMATH — the first resource for mathematics

On sets polynomially enumerable by iteration. (English) Zbl 0745.68047
Summary: Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets — including all exponential-time complete sets, all \(NP\)-complete sets yet obtained by direct construction, and the complements of all such sets — are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are \(\leq^ p_{1,si}\)-self-reducible are polynomially enumerable by iteration, and that all recursive sets that are \(\leq^ p_{1,si}\)- self-reducible are bi-enumerable. We also show that when the \(\leq^ p_{1,si}\)-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no \(NP\)-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to \(NP\). We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abadi, M.; Allender, E.; Broder, A.; Feigenbaum, J.; Hemachandra, L., On generating solved instances of computational problems, (), 297-310 · Zbl 0792.68045
[2] Adelman, L., Time, space, and randomness, ()
[3] Allender, E.; Rubinstein, R., P-printable sets, SIAM J. comput., 17, 6, 1193-1202, (1988) · Zbl 0682.68039
[4] Balcázar, J.; Book, R., Sets with small generalized Kolmogorov complexity, Acta inform., 23, 6, 679-688, (1986) · Zbl 0616.68046
[5] Berman, L., Polynomial reducibilities and complete sets, ()
[6] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, 2, 305-322, (1977) · Zbl 0356.68059
[7] D. Bruschi,, D. Joseph and P. Young, A structural overview of NP optimization problems, Algorithms Review, to appear. · Zbl 0704.68004
[8] Cai, J.; Hemachandra, L., On the power of parity polynomial time, Math. systems theory, 23, 95-106, (1990) · Zbl 0718.68038
[9] Davis, M., Computability and unsolvability, (1958), Dover New York · Zbl 0080.00902
[10] Ganesan, K.; Homer, S., Complete problems and strong polynomial reducibilities, (), 240-250 · Zbl 0749.68035
[11] J. Goldsmith, L. Hemachandra, D. Joseph and P. Young, Near-testable sets, SIAM J. Comput., to appear. · Zbl 0738.68031
[12] Goldsmith, J.; Hemachandra, L.; Kunen, K., On the structure and complexity of infinite sets with minimal perfect hash functions, () · Zbl 0925.68220
[13] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco, CA · Zbl 0411.68039
[14] Goldsmith, J.; Joseph, D.; Young, P., Self-reducible, P-selective, near-testable, and P-cheatable sets: the effect of internal structure on the complexity of a set, (), 50-59
[15] Goldschlager, L.; Parberry, I., On the construction of parallel computers from various bases of Boolean functions, Theoret. comput. sci., 43, 43-58, (1986) · Zbl 0604.68054
[16] Goldberg, A.; Sipser, M., Compression and ranking, Proc. 17th ACM symp. on theory of computing, 440-448, (1985)
[17] Grollmann, J.; Selman, A., Complexity measures for public-key cryptosystems, SIAM J. comput., 17, 309-335, (1988) · Zbl 0644.94016
[18] Hartmanis, J., Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24th IEEE symp. on foundations of computer science, 439-445, (1983)
[19] Hemachandra, L., Algorithms from complexity theory: polynomial-time operations for complex sets, (), 221-231 · Zbl 0819.68063
[20] Hermes, H., Zum begriff der axiomatisierbarkeit, Math. nachrichten, 4, 343-347, (1950-1951) · Zbl 0042.00704
[21] J. Hartmanis and L. Hemachandra, One-way functions and the non-isomorphism of NP-complete sets, Theoret. Comput. Sci. to appear. · Zbl 0718.03031
[22] Hartmanis, J.; Hemachandra, L., Complexity classes without machines: on complete languages for UP, Theoret. comput. sci., 58, 129-142, (1988) · Zbl 0655.68044
[23] Hartmanis, J.; Hemachandra, L., On sparse oracles separating feasible complexity classes, Inform. process. lett., 28, 291-295, (1988) · Zbl 0658.68055
[24] L. Hemachandra and A. Hoene, On sets with efficient implicit membership tests, SIAM J. Comput., to appear. · Zbl 0738.68032
[25] Hemachandra, L.; Hoene, A.; Stofkes, D., Polynomial-time functions generate SAT: on P-splinters, (), 259-269 · Zbl 0755.68067
[26] Hartmanis, J.; Immerman, N.; Sewelson, V., Sparse sets in NP-1 : EXPTIME versus NEXPTIME, Inform. and control, 65, 2/3, 159-181, (1985) · Zbl 0586.68042
[27] Hemachandra, L.; Rudich, S., On ranking, J. comput. system sci., 41, 251-271, (1990) · Zbl 0708.68020
[28] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[29] Huynh, D., The complexity of ranking simple languages, Math. systems theory, 23, 1-20, (1990) · Zbl 0692.68059
[30] Hartmanis, J.; Yesha, Y., Computation times of NP sets of different densities, Theoret. comput. sci., 34, 17-32, (1984) · Zbl 0985.68515
[31] Jerrum, M.; Valiant, L.; Vazirani, V., Random generation of combinatorial structures from a uniform distribution, Theoret. comput. sci., 43, 2,3, 169-188, (1986) · Zbl 0597.68056
[32] Joseph, D.; Young, P., Some remarks on witness functions for non-polynomial and non-complete sets in NP, Theoret. comput. sci., 39, 225-237, (1985) · Zbl 0597.68042
[33] Joseph, D.; Young, P., Self-reducibility: effects of internal structure on computational complexity, (), 82-107
[34] Köbler, J.; Schöning, U.; Toda, S.; Torán, J., Turing machines with few accepting computations and low sets for PP, (), 208-215
[35] Kurtz, S., A relativized failure of the berman-hartmanis conjecture, ()
[36] Mahaney, S.; Young, P., Reductions among polynomial isomorphism types, Theoret. comput. sci., 39, 207-224, (1985) · Zbl 0595.03042
[37] Myhill, J., Recursive digraphs, splinters, and cylinders, Math. ann., 138, (1959) · Zbl 0087.25103
[38] Orponen, P.; Russo, D.; Schöning, U., Optimal approximations and polynomially levelable sets, SIAM J. comput., 15, 2, 399-408, (1986) · Zbl 0644.68054
[39] Pilchner, M.; Rardin, R.; Tovey, C., Polynomial constructibility and traveling salesman problems of intermediate complexity, ()
[40] Papadimitriou, C.; Zachos, S., Two remarks on the power of counting, (), 269-276
[41] Rackoff, C., Relativized questions involving probabilistic algorithms, J. ACM, 29, 1, 261-268, (1982) · Zbl 0477.68037
[42] Rogers, H., The theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[43] Sanchis, L., Test case construction for NP-hard problems, Proc. 26th ann. allerton conf. on communication, control, and computing, (1988)
[44] Selman, A., Polynomial time enumeration reducibility, SIAM J. comput., 7, 440-457, (1978) · Zbl 0386.68055
[45] Selman, A., Analogues of semirecursive sets and effective reducibilities to the study of NP complexity, Inform. and control, 52, 36-51, (1982) · Zbl 0504.03022
[46] Sipser, M., A complexity theoretic approach to randomness, Proc. 15th ACM symp. on theory of computing, 330-335, (1983)
[47] Stockmeyer, L., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024
[48] Shay, M.; Young, P., Characterizing the orders changed by program translators, Pacific J. math., 76, 485-490, (1978) · Zbl 0392.03029
[49] Toda, S., On the computational power of PP and ⊕P, (), 514-519
[50] Torenvliet, L., Structural concepts in relativized hierarchies, ()
[51] Ullian, J., Splinters of recursive functions, J. symbolic logic, 25, 33-38, (1960) · Zbl 0112.00805
[52] Valiant, L., The relative complexity of checking and evaluating, Inform. process. lett., 5, 20-23, (1976) · Zbl 0342.68028
[53] Watanabe, O., On one-one P-equivalence relations, Theoret. comput. sci., 38, 157-165, (1985) · Zbl 0582.68016
[54] Watanabe, O., A note on the P-isomorphism conjecture, Theoret. comput. sci., 84, (1991), to appear
[55] Wrathall, C., Complete sets and the polynomial-time hierarchy, Theoret. comput. sci., 3, 23-33, (1977) · Zbl 0366.02031
[56] Young, P., On semi-cylinders, splinters, and bounded-truth-table reducibility, Trans. AMS, 115, 329-339, (1965) · Zbl 0163.25203
[57] Young, P., A theorem on recursively enumerable classes and splinters, Proc. AMS, 17, 1050-1056, (1966) · Zbl 0207.30601
[58] Young, P., On pseudo-creative sets, splinters, and bounded-truth-table reducibility, Z. math. logik grundlagen math., 13, 25-31, (1967) · Zbl 0207.30602
[59] Young, P., Toward a theory of enumerations, J. ACM, 16, 328-348, (1969) · Zbl 0191.30801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.