Characterizing polynomial Ramsey quantifiers

DOI10.1017/S0960129518000397zbMATH Open1422.68097arXiv1601.02258OpenAlexW2238496257WikidataQ128310638 ScholiaQ128310638MaRDI QIDQ5377702FDOQ5377702

Authors: Ronald de Haan, Jakub Szymanik 

Publication date: 27 May 2019

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1601.02258

Recommendations

• A dichotomy result for Ramsey quantifiers
• Logical hierarchies in PTIME
• Definability of polyadic lifts of generalized quantifiers
• Lower bounds for RAMs and quantifier elimination
• Relational queries computable in polynomial time

zbMATH Keywords

exponential time hypothesisgeneralized quantifiersRamsey propertiescomputational complexity dichotomy

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Descriptive complexity and finite models (68Q19)

Cites Work

• Quantifiers and cognition: logical and computational perspectives
• Computational Complexity
• Parametrized complexity theory.
• On the Structure of Polynomial Time Reducibility
• Lower bounds based on the exponential time hypothesis
• The complexity of satisfiability problems
• On the complexity of \(k\)-SAT
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite model theory and its applications.
• Strong computational lower bounds via parameterized complexity
• Tight lower bounds for certain parameterized NP-hard problems
• Henkin quantifiers and complete problems
• Henkin quantifiers: logic, games, and computation.
• Computational complexity of the semantics of some natural language constructions
• Definability of polyadic lifts of generalized quantifiers
• Unary quantifiers on finite models
• Dichotomy result for independence-friendly prefixes of generalized quantifiers
• The inapproximability of non-NP-hard optimization problems.
• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents

Cited In (2)

• A dichotomy result for Ramsey quantifiers
• Ramsey graphs cannot be defined by real polynomials

This page was built for publication: Characterizing polynomial Ramsey quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377702)