Equivariant algorithms for constraint satisfaction problems over coset templates

DOI10.1016/J.IPL.2016.09.009zbMATH Open1392.68386arXiv1412.4020OpenAlexW2963683868MaRDI QIDQ344534FDOQ344534

Authors: Sławomir Lasota 

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We investigate the Constraint Satisfaction Problem (CSP) over templates with a group structure, and algorithms solving CSP that are equivariant, i.e. invariant under a natural group action induced by a template. Our main result is a method of proving the implication: if CSP over a coset template T is solvable by an equivariant algorithm then T is 2-Helly (or equivalently, has a majority polymorphism). Therefore bounded width, and definability in fixed-point logics, coincide with 2-Helly. Even if these facts may be derived from already known results, our new proof method has two advantages. First, the proof is short, self-contained, and completely avoids referring to the omitting-types theorems. Second, it brings to light some new connections between CSP theory and descriptive complexity theory, via a construction similar to CFI graphs.

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

Recommendations

• Universal algebraic methods for constraint satisfaction problems
• The complexity of constraint satisfaction: an algebraic approach
• scientific article; zbMATH DE number 1670830
• Principles and Practice of Constraint Programming – CP 2004
• Constraint Satisfaction with Countable Homogeneous Templates
• Computer Science Logic
• The constraint satisfaction problem and universal algebra
• scientific article; zbMATH DE number 4162262
• Universal algebra and hardness results for constraint satisfaction problems
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems

zbMATH Keywords

constraint satisfaction problemscombinatorial problemsbounded widthcoset templateslocal consistency algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Descriptive complexity and finite models (68Q19)

Cites Work

• Arities of permutation groups: Wreath products and \(k\)-sets
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The collapse of the bounded width hierarchy
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The structure of finite algebras
• Generalized Majority-Minority Operations are Tractable
• A Simple Algorithm for Mal'tsev Constraints
• An optimal lower bound on the number of variables for graph identification
• Title not available (Why is that?)
• Bounded width problems and algebras
• Affine systems of equations and counting infinitary logic
• Constraint Satisfaction Problems of Bounded Width
• Turing machines with atoms

This page was built for publication: Equivariant algorithms for constraint satisfaction problems over coset templates

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