Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

3-10-2017

Journal or Book Title

arxiv

Abstract

After substantial progress over the last 15 years, the “algebraic CSP-dichotomy conjec- ture” reduces to the following: every local constraint satisfaction problem (CSP) associ- ated 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, there remain exam- ples of small algebras with just a single binary operation whose CSP resists classification as either tractable or NP-complete using known methods. In this paper we present some new methods for approaching this problem, with particular focus on those techniques that help us attack the class of finite algebras known as “commutative idempotent bi- nars” (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 manuscript made available through arxiv: https://arxiv.org/abs/1611.02867.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Included in

Algebra Commons

Share

COinS