| Summary: | 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.
|
|---|