#### Date

1-4-2016 12:00 AM

#### Major

Mathematics

#### Department

Mathematics

#### College

College of Liberal Arts and Sciences

#### Project Advisor

William DeMeo and Clifford Bergman

#### Project Advisor's Department

Mathematics

#### Description

A constraint satisfaction problem (CSP) asks for an assignment of appropriate values to variables subject to a given set of constraints. Examples of CSPs are found in virtually every technical discipline. We would like to discover methods for deciding when a CSP is “easy,” or tractable and when it is “hard” or intractable. Theories from universal algebra have turned out to be applicable in obtaining results on the tractability of CSPs. Specifically, each CSP can be converted to an algebra. The so-called absorption property of an algebra plays a key role in proofs related to the complexity of the corresponding CSPs. We developed some methods that enabled us to classify those absorption-free 4-element members of a certain class of algebras, called commutative idempotent binars (CIBs), which are not known to be tractable. Moreover, we determined the absorbing subalgebras of each 4-element CIB that is not absorption-free. Previously, few examples of either absorption-free CIBs or CIBs with absorbing subalgebras were known. This recent progress has therefore added to the general knowledge of the tractability of algebras and their corresponding CSPs.

#### File Format

application/pdf

#### Included in

Algebraic Approach to Constraint Satisfaction Problems

A constraint satisfaction problem (CSP) asks for an assignment of appropriate values to variables subject to a given set of constraints. Examples of CSPs are found in virtually every technical discipline. We would like to discover methods for deciding when a CSP is “easy,” or tractable and when it is “hard” or intractable. Theories from universal algebra have turned out to be applicable in obtaining results on the tractability of CSPs. Specifically, each CSP can be converted to an algebra. The so-called absorption property of an algebra plays a key role in proofs related to the complexity of the corresponding CSPs. We developed some methods that enabled us to classify those absorption-free 4-element members of a certain class of algebras, called commutative idempotent binars (CIBs), which are not known to be tractable. Moreover, we determined the absorbing subalgebras of each 4-element CIB that is not absorption-free. Previously, few examples of either absorption-free CIBs or CIBs with absorbing subalgebras were known. This recent progress has therefore added to the general knowledge of the tractability of algebras and their corresponding CSPs.