On the complexity of symmetric vs. functional PCSPs

Abstract

The complexity of the promise constraint satisfaction problem $\mathrm{PCSP}(\mathbf{A},\mathbf{B})$ is largely unknown, even for symmetric $\mathbf{A}$ and $\mathbf{B}$, except for the case when $\mathbf{A}$ and $\mathbf{B}$ are Boolean. First, we establish a dichotomy for $\mathrm{PCSP}(\mathbf{A},\mathbf{B})$ where $\mathbf{A},\mathbf{B}$ are symmetric, $\mathbf{B}$ is functional (i.e. any $r-1$ elements of an $r$-ary tuple uniquely determines the last one), and $(\mathbf{A},\mathbf{B})$ satisfies technical conditions we introduce called dependency and additivity. This result implies a dichotomy for $\mathrm{PCSP}(\mathbf{A},\mathbf{B})$ with $\mathbf{A},\mathbf{B}$ symmetric and $\mathbf{B}$ functional if (i) $\mathbf{A}$ is Boolean, or (ii) $\mathbf{A}$ is a hypergraph of a small uniformity, or (iii) $\mathbf{A}$ has a relation $R^{\mathbf{A}}$ of arity at least 3 such that the hypergraph diameter of $(A,R^{\mathbf{A}})$ is at most 1. Second, we show that for $\mathrm{PCSP}(\mathbf{A},\mathbf{B})$, where $\mathbf{A}$ and $\mathbf{B}$ contain a single relation, $\mathbf{A}$ satisfies a technical condition called balancedness, and $\mathbf{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 $\mathbf{A}$ include symmetric $\mathbf{A}$ or, more generally, $\mathbf{A}$ preserved by a transitive permutation group.

Full version (with stronger results) of a LICS'23 paper

References in corpus (4)

• CLAP: A New Algorithm for Promise CSPs
• An invitation to the promise constraint satisfaction problem
• Linearly ordered colourings of hypergraphs
• Beyond PCSP (1-in-3,NAE)

Cited by in corpus (2)

• Solving promise equations over monoids and groups
• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise