On polynomial-time truth-table reduciblity of intractable sets to p- selective sets. (English) Zbl 0722.68059

Summary: The existence of sets not being \(\leq^{P}_{tt}\)-reducible to low sets is investigated for several complexity classes such as UP, NP, the polynomial-time hierarchy, PSPACE, and EXPTIME. The p-selective sets are mainly considered as a class of low sets. Such investigations were done in many earlier works, but almost all of these have dealt with positive reductions in order to imply the strongest consequence such as \(P=NP\) under the assumption that all sets in NP are polynomial-time reducible to low sets. Currently, there seems to be some difficulty in obtaining the same strong results under nonpositive reducibilities. The purpose of this paper is to develop a useful technique to show for many complexity classes that if each set in the class is polynomial-time reducible to a p-selective set via a nonpositive reduction, then the class is already contained in P. The following results are shown:
(1) If each set in UP is \(\leq^{P}_{tt}\)-reducible to a p-selective set, then \(P=UP.\)
(2) If each set in NP is \(\leq^{P}_{tt}\)-reducible to a p-selective set, then \(P=FewP\) and \(R=NP.\)
(3) If each set in \(\Delta^{P}_{2}\) is \(\leq^{P}_{tt}\)-reducible to a p-selective set, then \(P=NP.\)
(4) If each set in PSPACE is \(\leq^{P}_{tt}\)-reducible to a p- selective set, then \(P=PSPACE.\)
(5) There is a set in EXPTIME that is not \(\leq^{P}_{tt}\)-reducible to any p-selective set.
It remains open whether \(P=NP\) follows from a weaker assumption that each set in NP is \(\leq^{P}_{tt}\)-reducible to a p-selective set.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI


[1] L. Adleman, Two theorems on random polynomial time,Proc. 17th Ann. Symposium on Foundations of Computer Science (1978), pp. 75–83.
[2] E. Allender, The complexity of sparse sets in P,Proc. 1st IEEE Conference on Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223 (1986), Springer-Verlag, Berlin, pp. 1–11. · Zbl 0608.68035
[3] A. Amir and W. I. Gasarch, Polynomial terse sets,Inform. and Computation 77 (1988), 37–56. · Zbl 0646.68049
[4] R. Beigel, A structural theorem that depends quantitatively on the complexity of SAT,Proc. 2nd Conference on Structure in Complexity Theory (1987), pp. 28–34.
[5] R. Beigel, NP-hard sets are p-superterse unless R = NP, Technical Report 88-04, Department of Computer Science, The Johns Hopkins University (1988).
[6] L. Berman, Relationship between density and deterministic complexity of NP-complete languages,Proc. 5th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 62 (1978), Springer-Verlag, Berlin, pp. 63–71. · Zbl 0382.68068
[7] L. Berman and J. Hartmanis, On isomorphism and densities of NP and other complete sets,SIAM J. Comput. 6 (1977), 305–322. · Zbl 0356.68059
[8] R. V. Book, Tally languages and complexity classes,Inform. and Control 26 (1974), 186–193. · Zbl 0287.68029
[9] R. V. Book and K. Ko, On sets truth-table reducible to sparse sets,SIAM J. Comput. 17 (1988), 903–919. · Zbl 0665.68040
[10] R. V. Book, C. Wrathall, A. L. Selman, and D. Dobkin, Inclusion complete tally languages and the Hertmanis-Berman conjecture,Math. Systems Theory 11 (1977), 1–8. · Zbl 0365.68044
[11] S. Even, A. L. Selman, and Y. Yacobi, The complexity of promise problems with applications to public-key cryptography,Inform. and Control 61 (1984), 114–133. · Zbl 0592.94012
[12] S. Fortune, A note on sparse complete sets,SIAM J. Comput. 8 (1979), 431–433. · Zbl 0415.68006
[13] J. Gill, Computational complexity of probabilistic Turing machines,SIAM J. Comput. 6 (1977), 675–695. · Zbl 0366.02024
[14] J. Grollmann and A. L. Selman, Complexity measure for public-key cryptosystems,SIAM J. Comput. 17 (1988), 309–335. · Zbl 0644.94016
[15] J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285–306. · Zbl 0131.15404
[16] J. Kadin, P NP[log] and sparse Turing-complete sets for NP,Proc. 2nd IEEE Conference on Structure in Complexity Theory (1987), pp. 33–40.
[17] R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes,Proc. 12th ACM Ann. Symposium on Theory of Computing (1980), pp. 302–309.
[18] K. Ko, On self-reducibility and weak p-selectivity, J. Comput. System Sci.26 (1983), 209–221. · Zbl 0519.68062
[19] K. Ko and U. Schöning, On circuit-size complexity and the low hierarchy in NP,SIAM J. Comput. 14 (1985), 41–51. · Zbl 0562.68033
[20] T. J. Long, A note on sparse oracles for NP,J. Comput. System Sci. 24 (1982), 224–232. · Zbl 0486.68033
[21] T. J. Long, On restricting the size of oracles compared with restricting access to oracles,SIAM J. Comput. 14 (1985), 585–597. · Zbl 0583.68025
[22] S. Mahaney, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis,J. Comput. System Sci. 25 (1982), 130–143. · Zbl 0493.68043
[23] M. Ogiwara and O. Watanabe, On polynomial time bounded truth-table reducibility of NP sets to sparse sets,Proc. 22nd ACM Symposium on Theory of Computing (1990), pp. 457–467. · Zbl 0741.68049
[24] U. Schöning, A low and a high hierarchy within NP,J. Comput. System Sci. 27 (1983), 14–28. · Zbl 0515.68046
[25] U. Schöning,Complexity and Structure, Lecture Notes in Computer Science, Vol. 211 (1985), Springer-Verlag, Berlin.
[26] A. L. Selman, P-selective sets, tally languages, and the behavior of polynomial reducibilities on NP,Math. Systems Theory 13 (1979), 55–65. · Zbl 0415.03031
[27] A. L. Selman, Some observations on NP real numbers and p-selective sets,J. Comput. System Science 23 (1981), 326–332. · Zbl 0486.03020
[28] A. L. Selman, Analogues of semi-recursive sets and effective reducibilities to the study of NP complexity,Inform. and Control 52 (1982), 36–51. · Zbl 0504.03022
[29] A. L. Selman, Reductions on NP and p-selective sets,Theoret. Comput. Sci. 19 (1982), 287–304. · Zbl 0489.03016
[30] L. J. Stockmeyer, The polynomial-time hierarchy,Theoret. Comput. Sci. 3 (1977), 1–22. · Zbl 0353.02024
[31] E. Ukkonen, Two results on polynomial time Turing reductions to sparse sets,SIAM J. Comput. 12 (1983), 580–587. · Zbl 0532.68051
[32] L. G. Valiant, Relative complexity of checking and evaluating,Inform. Process. Lett. 5 (1976), 20–23. · Zbl 0342.68028
[33] L. G. Valiant and V. V. Vazirani, NP is as easy as detecting unique solutions,Theoret. Comput. Sci. 47 (1986), 85–93. · Zbl 0621.68030
[34] O. Watanabe, Polynomial time reducibility to a set of small density,Proc. 2nd IEEE Conference on Structure in Complexity Theory (1987), pp. 138–146.
[35] O. Watanabe, On hardness of one-way functions,Inform. Process. Lett. 27 (1988), 151–157. · Zbl 0635.68037
[36] O. Watanabe, On 1t P -sparseness and nondeterministic complexity classes,J, Comput. System Science, to appear.
[37] O. Watanabe, Polynomial time truth-table reducibility to p-selective sets, unpublished manuscript (1990).
[38] C. Wrathall, Complete sets and the polynomial-time hierarchy,Theoret. Comput. Sci. 3 (1977), 23–33. · Zbl 0366.02031
[39] C. Yap, Some consequences of non-uniform conditions on uniform classes,Theoret. Comput. Sci. 27 (1983), 287–300. · Zbl 0541.68017
[40] Y. Yesha, On certain polynomial-time truth-table reductions to sparse sets,SIAM J. Comput. 12 (1983), 411–425, · Zbl 0545.03023
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.