Asking the Metaquestions in Constraint Tractability

DOI10.1145/3134757zbMath1427.68115arXiv1604.00932OpenAlexW2963295189MaRDI QIDQ4973888

Hubie Chen, Benoit Larose

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

homomorphismsconstraint satisfactiontractabilitypolymorphismsmetaquestions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Local–global property for G-invariant terms ⋮ The smallest hard trees ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing the Complexity of a Valued CSP Language ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

This page was built for publication: Asking the Metaquestions in Constraint Tractability