On the complexity of symmetric vs. functional PCSPs

The complexity of the promise constraint satisfaction problem \(PCSP(A,B)\) is largely unknown, even for symmetric \(A\) and \(B\) , except for the case when \(A\) and \(B\) are Boolean. First, we establish a dichotomy for \(PCSP(A,B)\) where \(A,B\) are symmetric, \(B\) is functional (i.e. any \(r-1\) elements of an \(r\) -ary tuple uniquely determines the last one), and \((A,B)\) satisfies technical conditions we introduce called dependency and additivity . This result implies a dichotomy for \(PCSP(A,B)\) with \(A,B\) symmetric and \(B\) functional if (i) \(A\) is Boolean, or (ii) \(A\) is a hypergraph of a small uniformity, or (iii) \(A\) has a relation \(RA\) of arity at least 3 such that the hypergraph diameter of \((A,RA)\) is at most 1. Second, we show that for \(PCSP(A,B)\) , where \(A\) and \(B\) contain a single relation, \(A\) satisfies a technical condition called balancedness , and \(B\) is arbitrary, the combined basic linear programming relaxation ( \(BLP\) ) and the affine integer programming relaxation ( \(AIP\) ) is no more powerful than the (in general strictly weaker) \(AIP\) relaxation. Balanced \(A\) include symmetric \(A\) or, more generally, \(A\) preserved by a transitive permutation group.