  Promise Constraint Satisfaction Problems (PCSP) were proposed recently by
Brakensiek and Guruswami arXiv:1704.01937 as a framework to study
approximations for Constraint Satisfaction Problems (CSP). Informally a PCSP
asks to distinguish between whether a given instance of a CSP has a solution or
not even a specified relaxation can be satisfied. All currently known tractable
PCSPs can be reduced in a natural way to tractable CSPs. Barto arXiv:1909.04878
presented an example of a PCSP over Boolean structures for which this reduction
requires solving a CSP over an infinite structure. We give a first example of a
PCSP over Boolean structures which reduces to a tractable CSP over a structure
of size $3$ but not smaller. Further we investigate properties of PCSPs that
reduce to systems of linear equations or to CSPs over structures with
semilattice or majority polymorphism.
