Hide menu

News 2016

New algebraic methods to study the complexity of constraint satisfaction problems

Constraint satisfaction problems are an important type of computational problems with many applications within for example scheduling and optimisation problems. The so-called algebraic approach has for the past 20 years had tremendous success in identifying constraint satisfaction problems solvable in polynomial time. Since efficient algorithms exists for such problems, they are often said to be tractable. However, this algebraic approach cannot be used to study the worst-case time complexity for the problems that are not believed to be tractable, even though these problems can vary substantially in complexity.

To study the difference in complexity between hard constraint satisfaction problems of this kind, Victor Lagerkvist in his PhD thesis on IDA proposes an algebraic framework based on partial functions. This framework is then used to study the complexity for many well-known variants of the constraint satisfaction problem. The complexity for these problems is then related to a complexity theoretical conjecture, the exponential-time hypothesis, which states that there is a sharp limit to how much it is possible to improve exponential-time algorithms for constraint satisfaction problems.
Read more

Page responsible: Webmaster