Polynomial time bounded truth-table reducibilities to padded sets

Vladimír Glasnák

Commentationes Mathematicae Universitatis Carolinae (2000)

  • Volume: 41, Issue: 4, page 773-792
  • ISSN: 0010-2628

Abstract

top
We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class f -PAD of all f -padded sets, if it is a subset of { x 10 f ( | x | ) - | x | - 1 ; x ∈ { 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 m ( f -PAD ) ⊊ R 1 -tt ( f -PAD ) ⊊ ⋯ ⊊ R btt ( f -PAD ) , or R m ( f -PAD ) = R 1 -tt ( f -PAD ) ⊊ ⋯ ⊊ R btt ( f -PAD ) , or R m ( f -PAD ) = R btt ( f -PAD ) .

How to cite

top

Glasnák, Vladimír. "Polynomial time bounded truth-table reducibilities to padded sets." Commentationes Mathematicae Universitatis Carolinae 41.4 (2000): 773-792. <http://eudml.org/doc/248586>.

@article{Glasnák2000,
abstract = {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 $\lbrace x10^\{f(|x|)-|x|-1\};\,x\in \lbrace 0,1\rbrace ^*\rbrace $). 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\}). \]},
author = {Glasnák, Vladimír},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {computational complexity; sparse set; padded set; reducibility; computational complexity; sparse set; padded set; reducibility},
language = {eng},
number = {4},
pages = {773-792},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Polynomial time bounded truth-table reducibilities to padded sets},
url = {http://eudml.org/doc/248586},
volume = {41},
year = {2000},
}

TY - JOUR
AU - Glasnák, Vladimír
TI - Polynomial time bounded truth-table reducibilities to padded sets
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2000
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 41
IS - 4
SP - 773
EP - 792
AB - 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 $\lbrace x10^{f(|x|)-|x|-1};\,x\in \lbrace 0,1\rbrace ^*\rbrace $). 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}). \]
LA - eng
KW - computational complexity; sparse set; padded set; reducibility; computational complexity; sparse set; padded set; reducibility
UR - http://eudml.org/doc/248586
ER -

References

top
  1. Allender E., Limitations of the upward separation technique, Math. Systems Theory 24 (1991), 53-67. (1991) Zbl0708.68019MR1076125
  2. 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. 
  3. 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. MR1047862
  4. Buhrman H., Resource Bounded Reductions, PhD Thesis, Universiteit van Amsterdam, Amsterdam, 1993. MR1255342
  5. Berman L., Hartmanis J., On isomorphism and density of NP and other complete sets, SIAM J. Comput. 6 (1977), 305-327. (1977) MR0455536
  6. Buhrman H., Homer S., Torenvliet L., Completeness for nondeterministic complexity classes, Math. Systems Theory 24 (1991), 179-200. (1991) Zbl0745.68046MR1113612
  7. Book R., Ko K., On sets truth-table reducible to sparse sets, SIAM J. Comput. 17 (1988), 903-919. (1988) Zbl0665.68040MR0961047
  8. 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. Zbl0788.68049MR1255342
  9. Cook S.A., The complexity of theorem proving procedures, Proc. 3rd Annual Symposium on Theory of Computing, 1971, pp.151-158. Zbl0363.68125
  10. Glasnák V., Sparse sets and collapse of complexity classes, submitted for publication. 
  11. Hartmanis J., On sparse sets in NP - P, Inform. Process. Lett. 16 (1983), 55-60. (1983) Zbl0501.68014MR0696842
  12. Hartmanis J., Immerman N., Sewelson V., Sparse sets in NP - P: EXPTIME versus NEXPTIME, Inform. and Control 65 (1985), 158-181. (1985) Zbl0586.68042MR0818849
  13. 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. MR1249979
  14. 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. 
  15. Karp R. M., Reducibility among combinatorial problems, in Miller, Thatcher (ed.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp.302-309. Zbl0366.68041MR0378476
  16. Ko K., Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Inform. and Comput. 81 (1989), 62-87. (1989) Zbl0681.68066MR0992304
  17. Köbler J., Unterschung verschiedener polynomieller Reduktionsklassen von NP, Diplom. thesis, Institut für Informatik, Univ. Stuttgart, 1985. 
  18. Ladner R., Lynch N., Selman A., A comparison of polynomial-time reducibilities, Theoret. Comput. Sci. 1 (1973), 103-123. (1973) MR0395319
  19. Li M., Vitányi P., An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1993. MR1238938
  20. 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) Zbl0741.68049MR1094526
  21. Mahaney S., Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci. 25 (1982), 130-143. (1982) Zbl0493.68043MR0680515
  22. 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. MR1249980
  23. 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. 
  24. Schöning U., On random reductions from sparse to tally sets, Inform. Process. Lett. 46 (1993), 239-241. (1993) 
  25. Watanabe O., A comparison of polynomial time completeness notions, Theoret. Comput. Sci. 54 (1987), 249-265. (1987) Zbl0635.68035MR0919594

NotesEmbed ?

top

You must be logged in to post comments.