# Bounded queries to arbitrary sets

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

- Volume: 30, Issue: 2, page 91-100
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topLozano, A.. "Bounded queries to arbitrary sets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.2 (1996): 91-100. <http://eudml.org/doc/92532>.

@article{Lozano1996,

author = {Lozano, A.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {hierarchy of sets},

language = {eng},

number = {2},

pages = {91-100},

publisher = {EDP-Sciences},

title = {Bounded queries to arbitrary sets},

url = {http://eudml.org/doc/92532},

volume = {30},

year = {1996},

}

TY - JOUR

AU - Lozano, A.

TI - Bounded queries to arbitrary sets

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 1996

PB - EDP-Sciences

VL - 30

IS - 2

SP - 91

EP - 100

LA - eng

KW - hierarchy of sets

UR - http://eudml.org/doc/92532

ER -

## References

top- 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. Zbl0761.68039MR1163344
- 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. Zbl1058.68056MR1097673
- 3. R. BEIGEL, Query-limited Reducibilities, PhD thesis, Stanford University, 1987. MR2636225
- 4. R. BEIGEL, Bounded queries to SAT and the boolean hierarchy, Theoretical Computer Science, 1991, 84 (2), pp. 199-223. Zbl0739.68035MR1118121
- 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. Zbl0776.68043MR1209999
- 6. R. CHANG, On the structure of bounded queries to arbitrary NP sets, SIAM Journal on Computing, 1992, 21 (4), pp. 743-754. Zbl0749.68034MR1171859
- 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. Zbl0844.68048MR1097667
- 8. F. GREEN, On the power of deterministic reductions to C = P, Manuscript, April 1991.
- 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. MR1097665
- 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. Zbl0664.03031
- 13. J. KADIN, The polynomial time hierarchy collapses if the boolean hierarchy collapses, SIAM Journal on Computing, 1988, 17 (6), pp. 1263-1282. Zbl0664.03031MR972673
- 14. J. KADIN, Erratum to [13], SIAM Journal on Computing, 1991, 20 (2), p. 104. MR1087757
- 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. Zbl0321.68039MR395319
- 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. Zbl0813.68105MR1264385
- 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. Zbl0798.68060MR1228809
- 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. Zbl0733.68035
- 21. K. W. WAGNER, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. Zbl0621.68032MR853581