Polynomial time bounded truth-table reducibilities to padded sets
Glasnák, Vladimír
Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000), p. 773-792 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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}). $$

Publié le : 2000-01-01
Classification:  03D15,  03D30,  68Q15,  68Q17 
@article{119209,
     author = {Vladim\'\i r Glasn\'ak},
     title = {Polynomial time bounded truth-table reducibilities to padded sets},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {41},
     year = {2000},
     pages = {773-792},
     zbl = {1051.03029},
     mrnumber = {1800166},
     language = {en},
     url = {http://dml.mathdoc.fr/item/119209}
}

Glasnák, Vladimír. Polynomial time bounded truth-table reducibilities to padded sets. Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000) pp. 773-792. http://gdmltest.u-ga.fr/item/119209/

Allender E. Limitations of the upward separation technique, Math. Systems Theory 24 (1991), 53-67. (1991) | MR 1076125 | Zbl 0708.68019

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.

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

Buhrman H. Resource Bounded Reductions, PhD Thesis, Universiteit van Amsterdam, Amsterdam, 1993. | MR 1255342

Berman L.; Hartmanis J. On isomorphism and density of NP and other complete sets, SIAM J. Comput. 6 (1977), 305-327. (1977) | MR 0455536

Buhrman H.; Homer S.; Torenvliet L. Completeness for nondeterministic complexity classes, Math. Systems Theory 24 (1991), 179-200. (1991) | MR 1113612 | Zbl 0745.68046

Book R.; Ko K. On sets truth-table reducible to sparse sets, SIAM J. Comput. 17 (1988), 903-919. (1988) | MR 0961047 | Zbl 0665.68040

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

Cook S.A. The complexity of theorem proving procedures, Proc. 3rd Annual Symposium on Theory of Computing, 1971, pp.151-158. | Zbl 0363.68125

Glasnák V. Sparse sets and collapse of complexity classes, submitted for publication.

Hartmanis J. On sparse sets in NP$-$P, Inform. Process. Lett. 16 (1983), 55-60. (1983) | MR 0696842 | Zbl 0501.68014

Hartmanis J.; Immerman N.; Sewelson V. Sparse sets in NP$-$P: EXPTIME versus NEXPTIME, Inform. and Control 65 (1985), 158-181. (1985) | MR 0818849 | Zbl 0586.68042

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

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.

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

Ko K. Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Inform. and Comput. 81 (1989), 62-87. (1989) | MR 0992304 | Zbl 0681.68066

Köbler J. Unterschung verschiedener polynomieller Reduktionsklassen von NP, Diplom. thesis, Institut für Informatik, Univ. Stuttgart, 1985.

Ladner R.; Lynch N.; Selman A. A comparison of polynomial-time reducibilities, Theoret. Comput. Sci. 1 (1973), 103-123. (1973) | MR 0395319

Li M.; Vitányi P. An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1993. | MR 1238938

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. (1991) | MR 1094526 | Zbl 0741.68049

Mahaney S. Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci. 25 (1982), 130-143. (1982) | MR 0680515 | Zbl 0493.68043

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

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.

Schöning U. On random reductions from sparse to tally sets, Inform. Process. Lett. 46 (1993), 239-241. (1993)

Watanabe O. A comparison of polynomial time completeness notions, Theoret. Comput. Sci. 54 (1987), 249-265. (1987) | MR 0919594 | Zbl 0635.68035