On sets bounded truth-table reducible to P-selective sets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 2, pp. 135-154. 
@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},
     pages = {135--154},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {2},
     year = {1996},
     mrnumber = {1420688},
     zbl = {0860.68050},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1996__30_2_135_0/}
}
TY  - JOUR
AU  - Thierauf, Thomas
AU  - Toda, Seinosuke
AU  - Watanabe, Osamu
TI  - On sets bounded truth-table reducible to $P$-selective sets
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 135
EP  - 154
VL  - 30
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_2_135_0/
LA  - en
ID  - ITA_1996__30_2_135_0
ER  - 
%0 Journal Article
%A Thierauf, Thomas
%A Toda, Seinosuke
%A Watanabe, Osamu
%T On sets bounded truth-table reducible to $P$-selective sets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 135-154
%V 30
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1996__30_2_135_0/
%G en
%F 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) no. 2, pp. 135-154. http://www.numdam.org/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

[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 | Zbl

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

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

[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

[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 | Zbl

[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

[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 | Zbl

[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

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

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

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

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

[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 | Zbl

[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 | Zbl

[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

[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 | Zbl

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

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

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

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

[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 | Zbl

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

[Wat90] O. Watanabe, Unpublished note.