| Title:
|
Polynomial time bounded truth-table reducibilities to padded sets (English) |
| Author:
|
Glasnák, Vladimír |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
41 |
| Issue:
|
4 |
| Year:
|
2000 |
| Pages:
|
773-792 |
| . |
| Category:
|
math |
| . |
| 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}). $$ (English) |
| Keyword:
|
computational complexity |
| Keyword:
|
sparse set |
| Keyword:
|
padded set |
| Keyword:
|
reducibility |
| MSC:
|
03D15 |
| MSC:
|
03D30 |
| MSC:
|
68Q15 |
| MSC:
|
68Q17 |
| idZBL:
|
Zbl 1051.03029 |
| idMR:
|
MR1800166 |
| . |
| Date available:
|
2009-01-08T19:07:15Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119209 |
| . |
| Reference:
|
[A1] Allender E.: Limitations of the upward separation technique.Math. Systems Theory 24 (1991), 53-67. Zbl 0708.68019, MR 1076125 |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[B1] Buhrman H.: Resource Bounded Reductions.PhD Thesis, Universiteit van Amsterdam, Amsterdam, 1993. MR 1255342 |
| Reference:
|
[BH1] Berman L., Hartmanis J.: On isomorphism and density of NP and other complete sets.SIAM J. Comput. 6 (1977), 305-327. MR 0455536 |
| Reference:
|
[BHT1] Buhrman H., Homer S., Torenvliet L.: Completeness for nondeterministic complexity classes.Math. Systems Theory 24 (1991), 179-200. Zbl 0745.68046, MR 1113612 |
| Reference:
|
[BK1] Book R., Ko K.: On sets truth-table reducible to sparse sets.SIAM J. Comput. 17 (1988), 903-919. Zbl 0665.68040, MR 0961047 |
| Reference:
|
[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. Zbl 0788.68049, MR 1255342 |
| Reference:
|
[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 |
| Reference:
|
[G1] Glasnák V.: Sparse sets and collapse of complexity classes.submitted for publication. |
| Reference:
|
[H1] Hartmanis J.: On sparse sets in NP$-$P.Inform. Process. Lett. 16 (1983), 55-60. Zbl 0501.68014, MR 0696842 |
| Reference:
|
[HIS1] Hartmanis J., Immerman N., Sewelson V.: Sparse sets in NP$-$P: EXPTIME versus NEXPTIME.Inform. and Control 65 (1985), 158-181. Zbl 0586.68042, MR 0818849 |
| Reference:
|
[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 |
| Reference:
|
[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. |
| Reference:
|
[K1] Karp R. M.: Reducibility among combinatorial problems.in Miller, Thatcher (ed.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp.302-309. Zbl 0366.68041, MR 0378476 |
| Reference:
|
[K2] Ko K.: Distinguishing conjunctive and disjunctive reducibilities by sparse sets.Inform. and Comput. 81 (1989), 62-87. Zbl 0681.68066, MR 0992304 |
| Reference:
|
[K3] Köbler J.: Unterschung verschiedener polynomieller Reduktionsklassen von NP.Diplom. thesis, Institut für Informatik, Univ. Stuttgart, 1985. |
| Reference:
|
[LLS1] Ladner R., Lynch N., Selman A.: A comparison of polynomial-time reducibilities.Theoret. Comput. Sci. 1 (1973), 103-123. MR 0395319 |
| Reference:
|
[LV1] Li M., Vitányi P.: An Introduction to Kolmogorov Complexity and its Applications.Springer-Verlag, New York, 1993. MR 1238938 |
| Reference:
|
[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. Zbl 0741.68049, MR 1094526 |
| Reference:
|
[M1] Mahaney S.: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis.J. Comput. System Sci. 25 (1982), 130-143. Zbl 0493.68043, MR 0680515 |
| Reference:
|
[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 |
| Reference:
|
[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. |
| Reference:
|
[S2] Schöning U.: On random reductions from sparse to tally sets.Inform. Process. Lett. 46 (1993), 239-241. |
| Reference:
|
[W1] Watanabe O.: A comparison of polynomial time completeness notions.Theoret. Comput. Sci. 54 (1987), 249-265. Zbl 0635.68035, MR 0919594 |
| . |
