Equivariant algorithms for constraint satisfaction problems over coset templates

DOI10.1016/J.IPL.2016.09.009MaRDI QIDQ344534zbMATH OpenOpenAlexFDO

Authors Sławomir Lasota

Publication date 23 November 2016

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• A Simple Algorithm for Mal'tsev Constraints
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Arities of permutation groups: Wreath products and \(k\)-sets
• Bounded width problems and algebras
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint Satisfaction Problems of Bounded Width
• Generalized Majority-Minority Operations are Tractable
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The collapse of the bounded width hierarchy
• The structure of finite algebras
• 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)