Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T08:46:25.903Z Has data issue: false hasContentIssue false
  • English
  • Français

Characterizing polynomial Ramsey quantifiers

Published online by Cambridge University Press:  28 February 2019

Ronald de Haan  and
Jakub Szymanik
Ronald de Haan
Affiliation:
Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands
Jakub Szymanik*
Affiliation:
Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Ramsey quantifiers are a natural object of study not only for logic and computer science but also for the formal semantics of natural language. Restricting attention to finite models leads to the natural question whether all Ramsey quantifiers are either polynomial-time computable or NP-hard, and whether we can give a natural characterization of the polynomial-time computable quantifiers. In this paper, we first show that there exist intermediate Ramsey quantifiers and then we prove a dichotomy result for a large and natural class of Ramsey quantifiers, based on a reasonable and widely believed complexity assumption. We show that the polynomial-time computable quantifiers in this class are exactly the constant-log-bounded Ramsey quantifiers.

Keywords

Keywords:Generalized quantifiersRamsey propertiescomputational complexity dichotomyExponential Time Hypothesis
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 29 , Issue 6 , June 2019 , pp. 896 - 908
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arora, S. and Barak, B. (2009). Computational Complexity– A Modern Approach. Cambridge University Press.CrossRefGoogle Scholar
Blass, A. and Gurevich, Y. (1986). Henkin quantifiers and complete problems. Annals of Pure and Applied Logic 32 1–16.CrossRefGoogle Scholar
Cai, L., Juedes, D. and Kanj, I. (2002). The inapproximability of non-NP-hard optimization problems. Theoretical Computer Science 289(1) 553–571.CrossRefGoogle Scholar
Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A. and Xia, G. (2005). Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201(2) 216–231.CrossRefGoogle Scholar
Chen, J., Huang, X., Kanj, I.A. and Xia, G. (2006). Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences 72(8) 1346–1367.CrossRefGoogle Scholar
Dalrymple, M., Kanazawa, M., Kim, Y., Mchombo, S. and Peters, S. (1998). Reciprocal expressions and the concept of reciprocity. Linguistics and Philosophy 21 159–210.CrossRefGoogle Scholar
Flum, J. and Grohe, M. (2006). Parameterized Complexity Theory. Springer, Berlin.Google Scholar
Grädel, E., Kolaitis, P. G., Libkin, L., Marx, M., Spencer, J., Vardi, M. Y., Venema, Y. and Weinstein, S. (2007). Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer.Google Scholar
Hella, L., Väänänen, J. and Westerståhl, D. (1997). Definability of polyadic lifts of generalized quantifiers. Journal of Logic, Language and Information 6(3) 305–335.CrossRefGoogle Scholar
Immerman, N. (1998). Descriptive Complexity. Texts in Computer Science. Springer, New York, NY.Google Scholar
Impagliazzo, R. and Paturi, R. (2001). On the complexity of k-SAT. Journal of Computer and System Sciences 62(2) 367–375.CrossRefGoogle Scholar
Ladner, R. E. (1975). On the structure of polynomial time reducibility. The Journal of the ACM 22(1) 155–171.CrossRefGoogle Scholar
Lokshtanov, D., Marx, D. and Saurabh, S. (2011). Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS 105 41–72.Google Scholar
Lindström, P. (1966). First order predicate logic with generalized quantifiers. Theoria 32 186–195.Google Scholar
Mostowski, M. and Wojtyniak, D. (2004). Computational complexity of the semantics of some natural language constructions. Annals of Pure and Applied Logic 127(1–3) 219–227.CrossRefGoogle Scholar
Peters, S. and Westerståhl, D. (2006). Quantifiers in Language and Logic, Clarendon Press, Oxford.Google Scholar
Ramsey, F. (1929). On a problem of formal logic. In: Proceedings of the London Mathematical Society. Vol. 30 of 2. London, London Mathematical Society, 338–384.Google Scholar
Schaefer, T. J. (1978). The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. STOC ’78, New York, NY, USA, ACM, 216–226.Google Scholar
Schlotterbeck, F. and Bott, O. (2013). Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents. Journal of Logic, Language and Information 22(4) 363–390.CrossRefGoogle Scholar
Sevenster, M. (2006). Branches of Imperfect Information: Logic, Games, and Computation. PhD thesis, Amsterdam, University of Amsterdam.Google Scholar
Sevenster, M. (2014). Dichotomy result for independence-friendly prefixes of generalized quantifiers. The Journal of Symbolic Logic 79(4) 1224–1246.CrossRefGoogle Scholar
Szymanik, J. (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. PhD thesis, University of Amsterdam, Amsterdam.Google Scholar
Szymanik, J. (2010). Computational complexity of polyadic lifts of generalized quantifiers in natural language. Linguistics and Philosophy 33 215–250.CrossRefGoogle Scholar
Szymanik, J. (2016). Quantifiers and cognition. Logical and computational perspectives. In: Studies in Linguistics and Philosophy. Springer.Google Scholar
Szymanik, J. and Thorne, C. (2017). Exploring the relation of semantic complexity and quantifier distribution in large corpora. Language Sciences 60 80–93.CrossRefGoogle Scholar
Väänänen, J. (1997). Unary quantifiers on finite models. Journal of Logic, Language and Information 6(3) 275–304.CrossRefGoogle Scholar