The complexity of counting quantifiers on equality languages

DOI10.1016/J.TCS.2017.01.022MaRDI QIDQ515549zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• The Complexity of Counting Quantifiers on Equality Languages
• The complexity of equality constraint languages
• Quantified Equality Constraints
• The Complexity of Equality Constraint Languages
• Constraint satisfaction with counting quantifiers

Cites work

• scientific article; zbMATH DE number 3968557 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Classifying the Complexity of Constraints Using Finite Algebras
• Constraint satisfaction with counting quantifiers
• On the complexity of H-coloring
• On the scope of the universal-algebraic approach to constraint satisfaction
• On uniformity within \(NC^ 1\)
• Positive First-Order Logic Is NP-Complete
• Quantified Equality Constraints
• Quantifiers and cognition: logical and computational perspectives
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Complexity of Abduction for Equality Constraint Languages
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of constraint satisfaction games and QCSP
• The complexity of equality constraint languages
• The complexity of satisfiability problems
• The polynomial-time hierarchy
• The reducts of equality up to primitive positive interdefinability
• Undirected connectivity in log-space

Cited in

(4)

• The Complexity of Equality Constraint Languages
• The Complexity of Counting Quantifiers on Equality Languages
• The Complexity of Abduction for Equality Constraint Languages
• The complexity of equality constraint languages

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

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