Clifford Bergman ; William DeMeo - Universal Algebraic Methods for Constraint Satisfaction Problems

lmcs:2568 - Logical Methods in Computer Science, January 19, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:12)2022
Universal Algebraic Methods for Constraint Satisfaction ProblemsArticle

Authors: Clifford Bergman ; William DeMeo

    After substantial progress over the last 15 years, the "algebraic CSP-dichotomy conjecture" reduces to the following: every local constraint satisfaction problem (CSP) associated with a finite idempotent algebra is tractable if and only if the algebra has a Taylor term operation. Despite the tremendous achievements in this area (including recently announce proofs of the general conjecture), there remain examples of small algebras with just a single binary operation whose CSP resists direct classification as either tractable or NP-complete using known methods. In this paper we present some new methods for approaching such problems, with particular focus on those techniques that help us attack the class of finite algebras known as "commutative idempotent binars" (CIBs). We demonstrate the utility of these methods by using them to prove that every CIB of cardinality at most 4 yields a tractable CSP.


    Volume: Volume 18, Issue 1
    Published on: January 19, 2022
    Accepted on: November 19, 2021
    Submitted on: December 1, 2016
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,Primary: 08A70, Secondary: 03C05, 08A30, 08A40
    Funding:
      Source : OpenAIRE Graph
    • Collaborative Research: Algebra and Algorithms, Structure and Complexity Theory; Funder: National Science Foundation; Code: 1500218

    Consultation statistics

    This page has been seen 2000 times.
    This article's PDF has been downloaded 669 times.