Journal of the ACM Bibliography
Jacobo Torán.
Complexity classes defined by counting quantifiers. Journal of the
ACM, 38(3):753-774, July 1991.
[BibTeX entry]
Categories and Subject Descriptors:
F.1.2 [Computation by Abstract Devices]: Modes of
Computation -- relativized computation; F.1.3
[Computation by Abstract Devices]: Complexity Classes
-- complexity hierarchies, relations among complexity
classes
General Terms:
Theory
Additional Key Words and Phrases:
Counting complexity classes
Selected papers that cite this one
- Eric Allender and Ulrich Hertrampf. Depth reduction for circuits of
unbounded fan-in. Information and Computation,
112(2):217-238, 1 August 1994.
- Richard Beigel, Nick Reingold, and Daniel Spielman. PP is closed under
intersection. Journal of Computer and System Sciences,
50(2):191-202, April 1995.
- K. Cronauer, U. Hertrampf, H. Vollmer, and K. W. Wagner. The chain method to
separate counting classes. Theory of Computing Systems,
31(1):93-108, January/February 1998.
- Bin Fu and Hong-Zhou Li. Closeness of NP-hard
sets to other complexity classes. SIAM Journal on
Computing, 23(2):255-260, April 1994.
- Lane A. Hemaspaandra and Mitsunori Ogihara. Universally
serializable computation. Journal of Computer and System
Sciences, 55(3):547-560, December 1997.
- J. Köbler and Seinosuke Toda. On the power of
generalized MOD-classes. Mathematical Systems Theory,
29(1):33-46, January/February 1996.
- Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe.
On closure
properties of #P in the context of PF \circ #P. Journal of
Computer and System Sciences, 53(2):171-179, October 1996.
- Heribert Vollmer and Klaus W. Wagner. Complexity classes of optimization
functions. Information and Computation, 120(2):198-219,
1 August 1995.
Selected references
- Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of
the ACM, 28(1):114-133, January 1981.
- Christos H. Papadimitriou. Games against nature
(extended abstract). In 24th Annual Symposium on Foundations
of Computer Science, pages 446-450, Tucson, Arizona, 7-9 November
1983. IEEE.
- Seinosuke Toda. On
the computational power of PP and oplus P. In 30th Annual
Symposium on Foundations of Computer Science, pages 514-519,
Research Triangle Park, North Carolina, 30 October-1 November 1989.
IEEE.
- Andrew Chi-Chih Yao. Separating the polynomial-time
hierarchy by oracles (preliminary version). In 26th Annual
Symposium on Foundations of Computer Science, pages 1-10,
Portland, Oregon, 21-23 October 1985. IEEE.
Shortcuts: