| Summary: | As our first result, we establish a dichotomy for promise constraint satisfaction problems of the form PCSP(A, B), where A is Boolean and symmetric and B is functional (on a domain of any size); i.e, all but one element of any tuple in a relation in B determine the last element. This includes PCSPs of the form PCSP(q-in-r, B), where B is functional, thus making progress towards a classification of PCSP(1-in-3, B), which were studied by Barto, Battistelli, and Berg [STACS’21] for B on three-element domains.As our second result, we show that for PCSP(A, B), where A contains a single symmetric relation and B is arbitrary (and thus not necessarily functional), the combined basic linear programming relaxation (BLP) and the affine integer programming relaxation (AIP) of Brakensiek et al. [SICOMP’20] is no more powerful than the (in general strictly weaker) AIP relaxation of Brakensiek and Guruswami [SICOMP’21].
|
|---|