By letting \(\mathbf {A}=\mathbf {B}\)  in the definition of a \(\operatorname{PCSP}\) , one obtains the standard (non-promise) constraint satisfaction problem (\(\operatorname{CSP}\) ) [1]}.
\(\operatorname{PCSPs}\)  were introduced by Austrin, Guruswami, and Håstad [2]} and Brakensiek and Guruswami [3]}
as a general framework for studying approximability of perfectly satisfiable \(\operatorname{CSPs}\)  and have
emerged as a new exciting direction in constraint satisfaction that requires different
techniques than \(\operatorname{CSPs}\) .It is customary to study \(\operatorname{(P)CSPs}\)  on more general objects than digraphs, known as relational structures [4]}, which consist of a collection of relations of arbitrary arities on a vertex set, cf. [4]}.
Recent works on \(\operatorname{PCSPs}\)  include
those using analytical methods [6]}, [7]}, [8]}, [9]}
and those building on algebraic methods [10]}, [11]}, [12]}, [13]}, [14]}, [15]}, [16]}, [17]}, [18]}, [19]}
developed in [4]}. However, most basic questions are still left open, including complexity classifications and applicability of different types of algorithms.
