Promise CSP (standard and seen from the other side)

Kristina Asimi, 27 Mar 2023

This talk will be divided into two parts. In the first part we will talk about the standard Promise CSP (PCSP), where a pair of relational structures (A,B) (such that there is a homomorphism from A to B) is fixed and PCSP(A,B) is defined as the problem of deciding whether an input structure has a homomorphism to A or not even to B. In the second part of the talk we propose a similar problem, where we restrict the left-hand side instead of the right-hand side, motivated by the so-called left-hand side restricted CSP. Namely, we fix a collection of pairs of relational structures C (such that for every pair there is a homomorphism from the first structure to the second one) and ask the following: for an input pair (A,B) from C and an input structure X, decide whether there is a homomorphism from B to X or not even from A to X.