Abstrakt
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.