Algebra Seminar talk
2024-06-14 13:30! ZS3!
Manuel Schweigler
An Algorithm for solving Constraint Satisfaction Problems with Few Subpowers
Abstract:
The Constraint Satisfaction Problem (CSP) framework includes a wide variety of computational problems. Each CSP consists of a set of variables and a set of constraints. A solution of a CSP is an assignment of variables such that all constraints are satisfied. If the relational structure A associated with the constraint relations has few subpowers (i.e. there are few subalgebras of powers of A), the CSP associated with A (CSP(A)) can be solved efficiently using the so-called few subpowers-algorithm. Having few subpowers is equivalent to the existence of a k-edge polymorphism. This polymorphism can be used to iteratively compute a representative subset of all possible solutions in polynomial time. Lastly, we show how this algorithm can be used to solve linear sets of equations.