Skip to content

Invitation to the lecture

8. February 2024
SJ2P11, Jesenná 5

Constraint satisfaction problems: an algebraic approach to classifying computational complexity

Lecturer: Žaneta Semanišinová / Institute of Algebra, Technical University Dresden, Germany

Date: February 8, 2024

Time: from 11:00 a.m. to 12:00 a.m.

Venue: SJ2P11, Jesenná 5, Košice


The Constraint Satisfiability Problem (CSP) provides a common framework for the study of a number of natural computational problems in different areas of mathematics and computer science, such as the satisfiability problem for logical formulas, the graph colorability problem, or various scheduling problems. In many cases there exist efficient algorithms to solve these problems (in polynomial time), in others we can prove that they are NP-hard and assume that no efficient algorithm exists to solve them. For a fixed relational structure B, CSP(B) is a problem whose input is a finite relational structure A and whose output is the answer to the question of whether there exists a homomorphism from A to B. In this talk, we will focus on an algebraic approach to classifying the complexity of CSP and on results concerning CSP on finite and infinite sets. Finally, we will consider an optimization variant of the CSP, the so-called Valued Constraint Satisfiability Problem.

Study at UPJŠ