A Dichotomy Result for Ramsey Quantifiers

DOI10.1007/978-3-662-47709-0_6zbMath1465.68099OpenAlexW1425958294MaRDI QIDQ2947460

Jakub Szymanik, Ronald de Haan

Publication date: 24 September 2015

Published in: Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47709-0_6

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of the semantics of some natural language constructions
• Finite model theory and its applications.
• Strong computational lower bounds via parameterized complexity
• Henkin quantifiers and complete problems
• Unary quantifiers on finite models
• Definability of polyadic lifts 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
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• On the Structure of Polynomial Time Reducibility
• DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS
• The complexity of satisfiability problems
• On the complexity of \(k\)-SAT

This page was built for publication: A Dichotomy Result for Ramsey Quantifiers