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

Mathematics Commons

Share

COinS
 
Apr 1st, 12:00 AM

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.