Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
computational complexity; sparse set; padded set; reducibility
computational complexity; sparse set; padded set; reducibility
Summary:
We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class $f\text{\it -PAD}$ of all $f$-padded sets, if it is a subset of $\{x10^{f(|x|)-|x|-1};\,x\in \{0,1\}^*\}$). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a function $f$ measuring ``holes'' in its image, one of the following three possibilities happen: $$ R_{\text{\rm m}}(f\text{\it -PAD})\subsetneq R_{1\text{\rm -tt}}(f\text{\it -PAD}) \subsetneq \dots \subsetneq R_{\text{\rm btt}}(f\text{\it -PAD}), \text{ or} \ R_{\text{\rm m}}(f\text{\it -PAD}) = R_{1\text{\rm -tt}}(f\text{\it -PAD})\subsetneq \dots \subsetneq R_{\text{\rm btt}}(f\text{\it -PAD}), \text{ or} \ R_{\text{\rm m}}(f\text{\it -PAD}) = R_{\text{\rm btt}}(f\text{\it -PAD}). $$
References:
[A1] Allender E.: Limitations of the upward separation technique. Math. Systems Theory 24 (1991), 53-67. MR 1076125 | Zbl 0708.68019
[AHH+1] Arvind V., Han Y., Hemachandra L., Köbler J., Lozano A., Mundhenk M., Ogiwara M., Schöning U., Silvestri R., Thierauf T.: Reductions to sets of low information content. in Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Springer-Verlag Lecture Notes in Computer Science, vol. 623, 1992, pp.162-173.
[BDG1] Balcázar J. L., Díaz J. and Gabarró J.: Structural complexity I. volume 11 of EATCS Monographs on Theoretical Computer Science, Springer Verlag, Berlin, 1988. MR 1047862
[B1] Buhrman H.: Resource Bounded Reductions. PhD Thesis, Universiteit van Amsterdam, Amsterdam, 1993. MR 1255342
[BH1] Berman L., Hartmanis J.: On isomorphism and density of NP and other complete sets. SIAM J. Comput. 6 (1977), 305-327. MR 0455536
[BHT1] Buhrman H., Homer S., Torenvliet L.: Completeness for nondeterministic complexity classes. Math. Systems Theory 24 (1991), 179-200. MR 1113612 | Zbl 0745.68046
[BK1] Book R., Ko K.: On sets truth-table reducible to sparse sets. SIAM J. Comput. 17 (1988), 903-919. MR 0961047 | Zbl 0665.68040
[BST1] Buhrman H., Spaan E., Torenvliet L.: Bounded reductions. in K. Ambos-Spies, S. Homer and U. Schöning, editors, Complexity Theory, Cambridge University Press, 1993, pp.83-99. MR 1255342 | Zbl 0788.68049
[C1] Cook S.A.: The complexity of theorem proving procedures. Proc. 3rd Annual Symposium on Theory of Computing, 1971, pp.151-158. Zbl 0363.68125
[G1] Glasnák V.: Sparse sets and collapse of complexity classes. submitted for publication.
[H1] Hartmanis J.: On sparse sets in NP$-$P. Inform. Process. Lett. 16 (1983), 55-60. MR 0696842 | Zbl 0501.68014
[HIS1] Hartmanis J., Immerman N., Sewelson V.: Sparse sets in NP$-$P: EXPTIME versus NEXPTIME. Inform. and Control 65 (1985), 158-181. MR 0818849 | Zbl 0586.68042
[HOW1] Hemachandra L., Ogiwara M., Watanabe O.: How hard are sparse sets?. in Proc. Structure in Complexity Theory seventh annual conference, pp.222-238; IEEE Computer Society Press, 1992. MR 1249979
[KL1] Karp R.M., Lipton R.J.: Some connections between uniform and nonuniform complexity classes. Proc. 12th ACM Symposium on Theory of Computing, 1980, pp.302-309.
[K1] Karp R. M.: Reducibility among combinatorial problems. in Miller, Thatcher (ed.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp.302-309. MR 0378476 | Zbl 0366.68041
[K2] Ko K.: Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Inform. and Comput. 81 (1989), 62-87. MR 0992304 | Zbl 0681.68066
[K3] Köbler J.: Unterschung verschiedener polynomieller Reduktionsklassen von NP. Diplom. thesis, Institut für Informatik, Univ. Stuttgart, 1985.
[LLS1] Ladner R., Lynch N., Selman A.: A comparison of polynomial-time reducibilities. Theoret. Comput. Sci. 1 (1973), 103-123. MR 0395319
[LV1] Li M., Vitányi P.: An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York, 1993. MR 1238938
[OW1] Ogiwara M., Watanabe O.: On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput. 20 3 (1991), 471-483. MR 1094526 | Zbl 0741.68049
[M1] Mahaney S.: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. J. Comput. System Sci. 25 (1982), 130-143. MR 0680515 | Zbl 0493.68043
[RR1] Ranjan D., Rohatgi P.: On randomized reductions to sparse sets. in Proceedings of the 7th Structure in Complexity Theory Conference, IEEE Computer Society Press, 1992, pp.239-242. MR 1249980
[S1] Saluja S.: Relativized limitations of left set technique and closure classes of sparse sets. Proc. of the 8th IEEE Conf. Structure in Complexity Theory, 1993, pp.215-222.
[S2] Schöning U.: On random reductions from sparse to tally sets. Inform. Process. Lett. 46 (1993), 239-241.
[W1] Watanabe O.: A comparison of polynomial time completeness notions. Theoret. Comput. Sci. 54 (1987), 249-265. MR 0919594 | Zbl 0635.68035
Search
Partner of
