Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

6-11-2020

Journal or Book Title

arxiv

Abstract

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.

Comments

This is a pre-print of the article Bergman, Clifford, and William DeMeo. "Universal Algebraic Methods for Constraint Satisfaction Problems." arXiv preprint arXiv:1611.02867 (2020). Posted with permission.

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Published Version

Included in

Algebra Commons

Share

COinS