Universal Algebraic Methods for Constraint Satisfaction Problems
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 t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2022-01-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2568/pdf |
| _version_ | 1797268527708635136 |
|---|---|
| author | Clifford Bergman William DeMeo |
| author_facet | Clifford Bergman William DeMeo |
| author_sort | Clifford Bergman |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:33:54Z |
| format | Article |
| id | doaj.art-e3198c28df80409cb3c865d8294dcbfb |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:33:54Z |
| publishDate | 2022-01-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-e3198c28df80409cb3c865d8294dcbfb2024-03-08T10:36:53ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742022-01-01Volume 18, Issue 110.46298/lmcs-18(1:12)20222568Universal Algebraic Methods for Constraint Satisfaction ProblemsClifford BergmanWilliam DeMeoAfter 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.https://lmcs.episciences.org/2568/pdfcomputer science - logic in computer sciencemathematics - logicprimary: 08a70, secondary: 03c05, 08a30, 08a40 |
| spellingShingle | Clifford Bergman William DeMeo Universal Algebraic Methods for Constraint Satisfaction Problems Logical Methods in Computer Science computer science - logic in computer science mathematics - logic primary: 08a70, secondary: 03c05, 08a30, 08a40 |
| title | Universal Algebraic Methods for Constraint Satisfaction Problems |
| title_full | Universal Algebraic Methods for Constraint Satisfaction Problems |
| title_fullStr | Universal Algebraic Methods for Constraint Satisfaction Problems |
| title_full_unstemmed | Universal Algebraic Methods for Constraint Satisfaction Problems |
| title_short | Universal Algebraic Methods for Constraint Satisfaction Problems |
| title_sort | universal algebraic methods for constraint satisfaction problems |
| topic | computer science - logic in computer science mathematics - logic primary: 08a70, secondary: 03c05, 08a30, 08a40 |
| url | https://lmcs.episciences.org/2568/pdf |
| work_keys_str_mv | AT cliffordbergman universalalgebraicmethodsforconstraintsatisfactionproblems AT williamdemeo universalalgebraicmethodsforconstraintsatisfactionproblems |