The complexity of counting quantifiers on equality languages

DOI10.1016/j.tcs.2017.01.022zbMath1359.68138OpenAlexW2583763929MaRDI QIDQ515549

Michał Wrona, Barnaby Martin, András Pongrácz

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/20827/1/20827.pdf

zbMATH Keywords

computational complexityconstraint satisfactioncounting quantifiersequality languagequantified constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantifiers and cognition: logical and computational perspectives
• The complexity of constraint satisfaction games and QCSP
• The complexity of equality constraint languages
• On the complexity of H-coloring
• The polynomial-time hierarchy
• On uniformity within \(NC^ 1\)
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
• The Complexity of Abduction for Equality Constraint Languages
• The reducts of equality up to primitive positive interdefinability
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Undirected connectivity in log-space
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Positive First-Order Logic Is NP-Complete
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Constraint Satisfaction with Counting Quantifiers
• Classifying the Complexity of Constraints Using Finite Algebras
• Quantified Equality Constraints
• The complexity of satisfiability problems

This page was built for publication: The complexity of counting quantifiers on equality languages