Algebraic Approach to Constraint Satisfaction Problems
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
The Honors project is potentially the most valuable component of an Honors education. Typically Honors students choose to do their projects in their area of study, but some will pick a topic of interest unrelated to their major.
The Honors Program requires that the project be presented at a poster presentation event. Poster presentations are held each semester. Most students present during their senior year, but may do so earlier if their honors project has been completed.
This site presents project descriptions and selected posters for Honors projects completed since the Fall 2015 semester.
Department
Abstract
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.