On sets bounded truth-table reducible to $P$-selective sets

 Access to full text

 Full (PDF)

1. [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. 
2. [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). Zbl0794.68058
3. [AI186] E. ALLENDER, The complexity of sparse sets in P, In Proceedings 1st Structure in Complexity Theory Conference, 1986, 1-11, IEEE Computer Society. Zbl0608.68035MR854886
4. [BDG88] J. BALCÁZAR, J. DÍAZ and J. GABARRÓ, Structural Complexity I. 1988, EATCS Monographs on Theoretical Computer Science, Springer-Verlag. Zbl0638.68040MR1047862
5. [BDG91] J. BALCÁZAR, J. DÍAZ and J. GABARRÓ, Structural Complexity II. 1991, EATCS Monographs on Theoretical Computer Science, Springer-Verlag. Zbl0746.68032MR1056474
6. [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. 
7. [BKS94] R. BEIGEL, M. KUMMER and F. STEPHAN, Approximable sets. In Poc. 9th Structure in Complexity Theory Conference, IEEE, 12-23, 1994. MR1343609
8. [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. Zbl0592.94012MR772678
9. [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. 
10. [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. MR1249979
11. [HL94] S. HOMER and L. LONGPRÉ, On Reductions of NP to Sparse Sets, Journal of Computer and System Sciences, 1994, 48, pp. 324-336. Zbl0806.68046MR1275036
12. [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. Zbl0873.68058MR1310807
13. [Joc68] C. JOCKUSCH, Semirecursive sets and positive reducibility, Transactions of the AMS, 1968, 131, (2), pp. 420-436. Zbl0198.32402MR220595
14. [KL82] R. KARP and R. LIPTON, Turing machines that take advice, L'Enseignement Mathématique, 1982, 28, pp. 191-209. Zbl0529.68025MR684233
15. [Ko83] K. KO, On self-reducibility and weak P-selectivity, Journal of Computer and System Sciences, 1983, 26, pp. 209-221. Zbl0519.68062MR708837
16. [LLS75] R. LADNER, N. LYNCH and A. SELMAN, A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1, (2), pp. 103-124. Zbl0321.68039MR395319
17. [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. Zbl0493.68043MR680515
18. [O94] M. OGIHRA, Polynomial-time membership comparable sets, In Proc. 9th Structure in Complexity Theory Conference, IEEE, 2-11, 1994. 
19. [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. Zbl0741.68049MR1094526
20. [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. 
21. [Sch90] U. SCHÖNING, The power of counting, In Complexity Theory Retrospective (A.Selman Ed.), Springer-Verlag, 1990, pp. 204-223. MR1060786
22. [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. Zbl0405.03018MR548549
23. [Sel82a] A. SELMAN, Analogues of Semirecursive sets and effective reducibilities to the study of NP complexity, Information and Control, 1982, pp.36-51. Zbl0504.03022MR693995
24. [Sel82b] A. SELMAN, Reductions on NP and P-selective sets, Theoretical Computer Science, 1982, 19, pp. 287-304. Zbl0489.03016MR671872
25. [Sto77] L. STOCKMEYER, The polynomial-time hierarchy, Theoretical Computer Science, 1977, 3, pp. 1-22. Zbl0353.02024MR438810
26. [Tod91] S. TODA, On polynomial-time truth-table reducibilities of intractable sets of P-selective sets, Mathematical Systems Theory, 1991, pp. 69-82. Zbl0722.68059MR1096692
27. [Tor93] J. TORÁN, Personal Communication. 
28. [Val76] L. VALIANT, Relative complexity of checking and evaluating, Information Processing Letters, 1976, 5, (1), pp. 20-23. Zbl0342.68028MR403318
29. [VV86] L. VALIANT and V. VAZIRANI, NP is as easy as detecting unique solutions, Theoretical Computer Science, 1986, 47, pp. 85-93. Zbl0621.68030MR871466
30. [Wat90] O. WATANABE, Unpublished note.