A logical characterization of the counting hierarchy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A logical characterization of the counting hierarchy

Full text

Pdf (185 KB)

Source

ACM Transactions on Computational Logic (TOCL) archive
Volume 10 , Issue 1 (January 2009) table of contents

Article No. 7

Year of Publication: 2009

ISSN:1529-3785

Author

Juha Kontinen

University of Helsinki, Helsinki, Finland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 88, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1459010.1459017 What is a DOI?

ABSTRACT

In this article we give a logical characterization of the counting hierarchy. The counting hierarchy is the analogue of the polynomial hierarchy, the building block being Probabilistic polynomial time PP instead of NP. We show that the extension of first-order logic by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We also consider extending the characterization to general proportional quantifiers Q^k_r interpreted as “more than an r-fraction of k-ary relations”. We show that the result holds for rational numbers of the form s/2^m but for any other 0 < r < 1 the corresponding logic satisfies the 0-1 law.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Allender, E., and Wagner, K. W. 1990. Counting hierarchies: Polynomial time and constant depth circuits. Bull. EATCS 40, 182--194.
	2	Andersson, A. 2002. On second-order generalized quantifiers and finite structures. Ann. Pure Appl. Logic 115, 1-3, 1--32.
	3	Richard Beigel , Nick Reingold , Daniel Spielman, PP is closed under intersection, Journal of Computer and System Sciences, v.50 n.2, p.191-202, April 1995
	4	Burtschick, H.-J., and Vollmer, H. 1998. Lindström quantifiers and leaf language definability. Int. J. Found. Comput. Sci. 9, 3, 277--294.
	5	Anuj Dawar , Erich Grädel, Generalized Quantifiers and 0-1 Laws, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.54, June 26-29, 1995
	6	Ebbinghaus, H.-D., and Flum, J. 1999. Finite model theory, 2nd edition. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, Germany.
	7	Fagin, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, American Mathematical Society, Providence, RI, 43--73.
	8	Fagin, R. 1976. Probabilities on finite models. J. Symb. Logic 41, 1, 50--58.
	9	Gill, J. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 4, 675--695.
	10	Glebskiǐ, J. V., Kogan, D. I., Liogon′kiǐ, M. I., and Talanov, V. A. 1969. Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics 5, 142--154.
	11	Gupta, S. 1990. A note on the counting hierarchy. Tech. Rep. OSU-CISRC-8/90-TR24, Computer and Information Research Center, Ohio State University.
	12	Immerman, N. 1999. Descriptive complexity. Graduate Texts in Computer Science. Springer-Verlag, Berlin, Germany.
	13	Knyazev, V. V. 1990. A zero-one law for an extension of the first-order predicate language. Kibernetika (Kiev) 2, 110--113.
	14	Kontinen, J. 2004. Definability of second order generalized quantifiers. http://www.helsinki.fi/~jkontine/. (Arch. Math. Logic, to appear).
	15	Kontinen, J. 2006. The hierarchy theorem for second order generalized quantifiers. J. Symb. Logic 71, 1, 188--202.
	16	Lindström, P. 1966. First order predicate logic with generalized quantifiers. Theoria 32, 186--195.
	17	Kerkko Luosto, Equicardinality on Linear Orders, Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, p.458-465, July 13-17, 2004 [doi>10.1109/LICS.2004.16]
	18	Mostowski, A. 1957. On a generalization of quantifiers. Fund. Math. 44, 12--36.
	19	Papadimitriou, C. H. 1994. Computational complexity. Addison-Wesley, Reading, MA.
	20	David Allen Russo, Structural properties of complexity classes (immunity, core), University of California, Santa Barbara, 1985
	21	Nicole Schweikardt, Arithmetic, first-order logic, and counting quantifiers, ACM Transactions on Computational Logic (TOCL), v.6 n.3, p.634-671, July 2005 [doi>10.1145/1071596.1071602]
	22	Janos Simon, On some central problems in computational complexity., Cornell University, Ithaca, NY, 1975
	23	Stockmeyer, L. J. 1976. The polynomial-time hierarchy. Theoret. Comput. Sci. 3, 1, 1--22.
	24	Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
	25	Jacobo Torán, Complexity classes defined by counting quantifiers, Journal of the ACM (JACM), v.38 n.3, p.752-773, July 1991 [doi>10.1145/116825.116858]
	26	Väänänen, J. 1999. Generalized quantifiers, an introduction. In Generalized Quantifiers and Computation (Aix-en-Provence, 1997). Lecture Notes in Computer Science, vol. 1754. Springer-Verlag, Berlin, Germany, 1--17.
	27	Heribert Vollmer, A Generalized Quantifier Concept in Computational Complexity Theory, Revised Lectures from the 9th European Summer School on Logic, Language, and Information: Generalized Quantifiers and Computation, p.99-123, August 11-22, 1997
	28	Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, v.23 n.3, p.325-356, June 1986 [doi>10.1007/BF00289117]