Algebraic Approach to Constraint Satisfaction Problems

Thumbnail Image
Date
2016-04-01
Authors
Thompson, Joshua
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Series
Honors Projects and Posters
University Honors Program

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
Mathematics
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.

Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright