Characterizing polynomial Ramsey quantifiers. (English) Zbl 1422.68097
Summary: 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.
MSC:
| 68Q19 | Descriptive complexity and finite models |
| 03C80 | Logic with extra quantifiers and operators |
Keywords:
generalized quantifiers; Ramsey properties; computational complexity dichotomy; exponential time hypothesisReferences:
| [1] | Arora, S. and Barak, B. (2009). Computational Complexity- A Modern Approach. Cambridge University Press. · Zbl 1193.68112 |
| [2] | Blass, A. and Gurevich, Y. (1986). Henkin quantifiers and complete problems. Annals of Pure and Applied Logic321-16. · Zbl 0618.03016 |
| [3] | Cai, L., Juedes, D. and Kanj, I. (2002). The inapproximability of non-NP-hard optimization problems. Theoretical Computer Science289(1) 553-571. · Zbl 1061.68059 |
| [4] | 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 Computation201(2) 216-231. · Zbl 1161.68476 |
| [5] | Chen, J., Huang, X., Kanj, I.A. and Xia, G. (2006). Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences72(8) 1346-1367. · Zbl 1119.68092 |
| [6] | Dalrymple, M., Kanazawa, M., Kim, Y., Mchombo, S. and Peters, S. (1998). Reciprocal expressions and the concept of reciprocity. Linguistics and Philosophy21159-210. |
| [7] | Flum, J. and Grohe, M. (2006). Parameterized Complexity Theory. Springer, Berlin. · Zbl 1143.68016 |
| [8] | 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. · Zbl 1133.03001 |
| [9] | Hella, L., Väänänen, J. and Westerståhl, D. (1997). Definability of polyadic lifts of generalized quantifiers. Journal of Logic, Language and Information6(3) 305-335. · Zbl 0880.03015 |
| [10] | Immerman, N. (1998). Descriptive Complexity. Texts in Computer Science. Springer, New York, NY. · Zbl 0945.03546 |
| [11] | Impagliazzo, R. and Paturi, R. (2001). On the complexity of k-SAT. Journal of Computer and System Sciences62(2) 367-375. · Zbl 0990.68079 |
| [12] | Ladner, R. E. (1975). On the structure of polynomial time reducibility. The Journal of the ACM22(1) 155-171. · Zbl 0322.68028 |
| [13] | Lokshtanov, D., Marx, D. and Saurabh, S. (2011). Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS10541-72. · Zbl 1258.68068 |
| [14] | Lindström, P. (1966). First order predicate logic with generalized quantifiers. Theoria32186-195. · Zbl 1230.03072 |
| [15] | Mostowski, M. and Wojtyniak, D. (2004). Computational complexity of the semantics of some natural language constructions. Annals of Pure and Applied Logic127(1-3) 219-227. · Zbl 1049.03025 |
| [16] | Peters, S. and Westerståhl, D. (2006). Quantifiers in Language and Logic, Clarendon Press, Oxford. |
| [17] | 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. · JFM 52.0046.01 |
| [18] | 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. · Zbl 1282.68143 |
| [19] | 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 Information22(4) 363-390. · Zbl 1305.68094 |
| [20] | Sevenster, M. (2006). Branches of Imperfect Information: Logic, Games, and Computation. PhD thesis, Amsterdam, University of Amsterdam. · Zbl 1169.68439 |
| [21] | Sevenster, M. (2014). Dichotomy result for independence-friendly prefixes of generalized quantifiers. The Journal of Symbolic Logic79(4) 1224-1246. · Zbl 1353.03016 |
| [22] | Szymanik, J. (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. PhD thesis, University of Amsterdam, Amsterdam. |
| [23] | Szymanik, J. (2010). Computational complexity of polyadic lifts of generalized quantifiers in natural language. Linguistics and Philosophy33215-250. |
| [24] | Szymanik, J. (2016). Quantifiers and cognition. Logical and computational perspectives. In: Studies in Linguistics and Philosophy. Springer. · Zbl 1432.03003 |
| [25] | Szymanik, J. and Thorne, C. (2017). Exploring the relation of semantic complexity and quantifier distribution in large corpora. Language Sciences6080-93. |
| [26] | Väänänen, J. (1997). Unary quantifiers on finite models. Journal of Logic, Language and Information6(3) 275-304. · Zbl 0880.03014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
