Bounded queries to arbitrary sets

Lozano, A.

Lozano, A.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 2, pp. 91-100.

MR Zbl

@article{ITA_1996__30_2_91_0,
     author = {Lozano, A.},
     title = {Bounded queries to arbitrary sets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {91--100},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {2},
     year = {1996},
     mrnumber = {1420685},
     zbl = {0860.68047},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1996__30_2_91_0/}
}

TY  - JOUR
AU  - Lozano, A.
TI  - Bounded queries to arbitrary sets
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 91
EP  - 100
VL  - 30
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_2_91_0/
LA  - en
ID  - ITA_1996__30_2_91_0
ER  -

%0 Journal Article
%A Lozano, A.
%T Bounded queries to arbitrary sets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 91-100
%V 30
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1996__30_2_91_0/
%G en
%F ITA_1996__30_2_91_0

Lozano, A. Bounded queries to arbitrary sets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 2, pp. 91-100. http://www.numdam.org/item/ITA_1996__30_2_91_0/

Bibliographie
Cité par

1. E. Allender, L. A. Hemachandra, M. Ogiwara, and O. Watanabe, Relating equivalence and reducibility to sparse sets, SIAM Journal on Computing, 1992, 2, pp. 521-539. | MR | Zbl

2. A. Amir, R. Beigel and W. I. Gasarch, Some connections between bounded query classes and non-uniform complexity, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 232-243. | MR

3. R. Beigel, Query-limited Reducibilities, PhD thesis, Stanford University, 1987. | MR

4. R. Beigel, Bounded queries to SAT and the boolean hierarchy, Theoretical Computer Science, 1991, 84 (2), pp. 199-223. | MR | Zbl

5. R. Beigel, R. Chang, and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies, Mathematical Systems Theory, 1993, 26 (3), pp. 293-310. | MR | Zbl

6. R. Chang, On the structure of bounded queries to arbitrary NP sets, SIAM Journal on Computing, 1992, 21 (4), pp. 743-754. | MR | Zbl

7. R. Chang and J. Kadin, The boolean hierarchy and the polynomial hierarchy: a closer connection, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 169-178. To appear in SIAM Journal on Computing. | MR | Zbl

8. F. Green, On the power of deterministic reductions to C = P, Manuscript, April 1991. | Zbl

9. T. Gunderman, N. Nasser, and G. Wechsung, A survey of counting classes, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 140-153. | MR

10. L. A. Hemachandra, Counting in structural complexity theory, PhD thesis, Cornell University, June 1987.

11. J. Kadin, IS one NP question as powerful as two?, Technical Report TR 87-842, Cornell University, June 1987.

12. J. Kadin, Restricted Turing reducibilities and the structure of the Polynomial Time Hierarchy, PhD thesis, Cornell University, February 1988.

13. J. Kadin, The polynomial time hierarchy collapses if the boolean hierarchy collapses, SIAM Journal on Computing, 1988, 17 (6), pp. 1263-1282. | MR | Zbl

14. J. Kadin, Erratum to [13], SIAM Journal on Computing, 1991, 20 (2), p. 104. | MR

15. R. E. Ladner, N. A. Lynch, and A. L. Selman, A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. | MR | Zbl

16. M. Ogiwara, On the computational power of exact counting, unpublished manuscript, April 1990.

17. M. Ogiwara, Generalized theorems on relationships among reducibility notions to certain complexity classes, Mathematical Systems Theory, 1984, 27, pp. 189-200. | MR | Zbl

18. M. Ogiwara and L. A. Hemachandra, A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46 (3), pp. 295-325. | MR | Zbl

19. J. Simon, On some central problems in computational complexity, PhD thesis, Cornell University, January 1975.

20. J. Torán, Structural properties of the Counting Hierarchy, PhD thesis, Universitat Politècnica de Catalunya, January 1990.

21. K. W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. | MR | Zbl