On sets bounded truth-table reducible to P-selective sets
Thierauf, Thomas ; Toda, Seinosuke ; Watanabe, Osamu
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 135-154 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1996-01-01
@article{ITA_1996__30_2_135_0,
     author = {Thierauf, Thomas and Toda, Seinosuke and Watanabe, Osamu},
     title = {On sets bounded truth-table reducible to $P$-selective sets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {30},
     year = {1996},
     pages = {135-154},
     mrnumber = {1420688},
     zbl = {0860.68050},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1996__30_2_135_0}
}

Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu. On sets bounded truth-table reducible to $P$-selective sets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) pp. 135-154. http://gdmltest.u-ga.fr/item/ITA_1996__30_2_135_0/

[AA94] M. Agrawal and V. Arvind, Polynomial-time truth-table reductions to P-selective sets, In Proc. 9th Structure in Complexity Theory Conference, 1994, IEEE, 24-30.

[AHH+93] V. Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri and T. Thierauf, Reductions to sets of low information content, Recent Developments in Complexity Theory, Cambridge University Press, (Also available as Technical Report TR-417, University of Rochester, Department of Computer Science, Rochester, NY, April 1992). | Zbl 0794.68058

[AI186] E. Allender, The complexity of sparse sets in P, In Proceedings 1st Structure in Complexity Theory Conference, 1986, 1-11, IEEE Computer Society. | MR 854886 | Zbl 0608.68035

[BDG88] J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. 1988, EATCS Monographs on Theoretical Computer Science, Springer-Verlag. | MR 1047862 | Zbl 0638.68040

[BDG91] J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II. 1991, EATCS Monographs on Theoretical Computer Science, Springer-Verlag. | MR 1056474 | Zbl 0746.68032

[Bei88] R. Beigel, NP-hard sets are P-superterse unless R = NP, Technical Report 88-04, Department of Computer Science, The John Hopkins University, 1988.

[BKS94] R. Beigel, M. Kummer and F. Stephan, Approximable sets. In Poc. 9th Structure in Complexity Theory Conference, IEEE, 12-23, 1994. | MR 1343609

[ESY84] S. Evan, A. Selman and Y. Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, 1984, 61, pp. 114-133. | MR 772678 | Zbl 0592.94012

[HHO+93] L. Hemachandra, A. Hoene, M. Ogiwara, A. Selman, T. Thierauf and J. Wang, Selectivity. In Proceedings of the 5th International Conference on Computation and Information, ICCI 93, IEEE, pp. 55-59, 1993.

[HOW92] L. Hemachandra, M. Ogiwara and O. Watanabe, How hard are sparse sets? In Proc. 7th Strcuture in Complexity Theory Conference, IEEE 222-238, 1992. | MR 1249979

[HL94] S. Homer and L. Longpré, On Reductions of NP to Sparse Sets, Journal of Computer and System Sciences, 1994, 48, pp. 324-336. | MR 1275036 | Zbl 0806.68046

[JT93] B. Jenner and J. Torán, Computing functions with parallel queries to NP, In Proc. 8th Structure in Complexity Theory Conference, IEEE 280-291, 1, 1993. | MR 1310807

[Joc68] C. Jockusch, Semirecursive sets and positive reducibility, Transactions of the AMS, 1968, 131, (2), pp. 420-436. | MR 220595 | Zbl 0198.32402

[KL82] R. Karp and R. Lipton, Turing machines that take advice, L'Enseignement Mathématique, 1982, 28, pp. 191-209. | MR 684233 | Zbl 0529.68025

[Ko83] K. Ko, On self-reducibility and weak P-selectivity, Journal of Computer and System Sciences, 1983, 26, pp. 209-221. | MR 708837 | Zbl 0519.68062

[LLS75] R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1, (2), pp. 103-124. | MR 395319 | Zbl 0321.68039

[Mah82] S. Mahaney, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, Journal of Computer and System Sciences, 1982, 25, pp. 130-143. | MR 680515 | Zbl 0493.68043

[O94] M. Ogihra, Polynomial-time membership comparable sets, In Proc. 9th Structure in Complexity Theory Conference, IEEE, 2-11, 1994.

[OW91] M. Ogiwara and O. Watanabe, On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing, 1991, 20, (3), pp.471-483. | MR 1094526 | Zbl 0741.68049

[Sal93] S. Saluja, Relativized limitations of the left settechnique andclosure classes of sparse sets, In Proc. 8th Structure in Complexity Theory Conference, IEEE, 215-222, 1993.

[Sch90] U. Schöning, The power of counting, In Complexity Theory Retrospective (A.Selman Ed.), Springer-Verlag, 1990, pp. 204-223. | MR 1060786

[Sel79] A. Selman, P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP, Mathematical Systems Theory, 1979, 13, pp. 55-65. | MR 548549 | Zbl 0405.03018

[Sel82a] A. Selman, Analogues of Semirecursive sets and effective reducibilities to the study of NP complexity, Information and Control, 1982, pp.36-51. | MR 693995 | Zbl 0504.03022

[Sel82b] A. Selman, Reductions on NP and P-selective sets, Theoretical Computer Science, 1982, 19, pp. 287-304. | MR 671872 | Zbl 0489.03016

[Sto77] L. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science, 1977, 3, pp. 1-22. | MR 438810 | Zbl 0353.02024

[Tod91] S. Toda, On polynomial-time truth-table reducibilities of intractable sets of P-selective sets, Mathematical Systems Theory, 1991, pp. 69-82. | MR 1096692 | Zbl 0722.68059

[Tor93] J. Torán, Personal Communication.

[Val76] L. Valiant, Relative complexity of checking and evaluating, Information Processing Letters, 1976, 5, (1), pp. 20-23. | MR 403318 | Zbl 0342.68028

[VV86] L. Valiant and V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, 1986, 47, pp. 85-93. | MR 871466 | Zbl 0621.68030

[Wat90] O. Watanabe, Unpublished note.