A Dichotomy Result for Ramsey Quantifiers
From MaRDI portal
Publication:2947460
DOI10.1007/978-3-662-47709-0_6zbMath1465.68099MaRDI 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
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