Characterizing polynomial Ramsey quantifiers

DOI10.1017/S0960129518000397MaRDI QIDQ5377702zbMATH OpenOpenAlexWikidataFDO

Authors Ronald de Haan, Jakub Szymanik

Publication date 27 May 2019

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

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

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)

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.

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

Cites work

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

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)