论文标题
关于对称与功能性PCSP的复杂性
On the complexity of symmetric vs. functional PCSPs
论文作者
论文摘要
承诺约束满意度问题的复杂性$ \ peratatorName {pcsp}（\ MathBf {a}，\ MathBf {b}）$在很大程度上是未知的，即使对于对称$ \ Mathbf {a} $和$ \ Mathbf {b} $的对称$ \ Mathbf {A a} $，除了$ \ m athbf $ \ the $ \ the $ \ the $ \ the $ \ the $ \\ a} a} a} a}布尔。 首先，我们为$ \ operatoTorname {pcsp}（\ mathbf {a}，\ mathbf {b}）$建立了二分法，其中$ \ m artbf {a}，\ mathbf {b} $是对称的，symortric，symmetric，$ \ mathbf {b} $ $ e $ $ - 最后一个）和$（\ mathbf {a}，\ mathbf {b}）$满足我们介绍的技术条件，称为依赖关系和添加性。该结果暗示了$ \ peratatOrName {pcsp}（\ MathBf {a}，\ Mathbf {b}）$，带有$ \ Mathbf {a}，\ Mathbf {a}，\ Mathbf {b} $ Symmetric and symmetric and $ \ mathbf {b} $ $ \ mathbf {a} $是一个小均匀性的超图，或（iii）$ \ mathbf {a} $具有关系$ r^{\ mathbf {a}} $，至少为3至少3个，以至于$（a，r^{a，r^{\ mathbff {a at at at at at at at at at y is at y hymerthaph aftraph ofertiations a arity of Arity of Arity to to HyperPraph atity 3。 Second, we show that for $\operatorname{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基本的线性编程松弛（BLP）和仿射整数编程松弛（AIP）并不比（一般而言严格弱）AIP放松更强大。均衡$ \ mathbf {a} $包括对称$ \ mathbf {a} $，或者更一般而言，$ \ mathbf {a} $由瞬时置换组保留。
The complexity of the promise constraint satisfaction problem $\operatorname{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 $\operatorname{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 $\operatorname{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 $\operatorname{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.
