Title:	CSP classification
DNr:	LiU-compute-2023-12
Project Type:	LiU Compute
Principal Investigator:	George Osipov <george.osipov@liu.se>
Affiliation:	Linköpings universitet
Duration:	2023-03-22 – 2023-08-01
Classification:	10201
Keywords:

Abstract

This work is for Gustav Andersson's master thesis supervised by Victor Lagerkvist and George Osipov. Constraint satisfaction problems (CSP) have applications in many different areas of computer science. They have been studied extensively both from the theoretical and practical points of view. In theory, a common way to study computational complexity of CSPs is to restrict the expressive power of constraints (fix a *constraint language*) and study whether the resulting CSP admits fast algorithms or is intractable. This line of research has been very active, culminating in the Dichotomy Theorem conjectured in 1998 and finally proven in 2017. One implication of the Dichotomy Theorem is the existence of a computable criterion distinguishing constraint languages that give rise to tractable vs intractable CSPs. However, computing this criterion in a naïve way is prohibitively slow. Our project is about designing a practical criterion for the meta-CSP problem. While theory also tells us that we are unlikely to achieve dramatic improvements in the running time when working over CSPs with large domains (i.e. when variables can takes many values), we can still hope for a practical implementation for smaller domains. Even this seemingly severe restriction poses a challenging problem in practice, and the resulting implementation can be very useful in the CSP research, e.g. for automatically checking conjectures.