论文标题
Borel CSP的代数方法
An algebraic approach to Borel CSPs
论文作者
论文摘要
我们将工具从代数方法中调整为约束满意度问题，以回答有关Borel CSP的描述性设置理论问题。我们表明，如果结构$ \ MATHCAL D $没有泰勒多态性，则相应的Borel CSP为$ \Mathbfς^1_2 $ -complete。 In particular, by the CSP Dichotomy Theorem, if $\operatorname{CSP}(\mathcal D)$ is $\mathrm{NP}$-complete, then the Borel version, $\operatorname{csp}_B(\mathcal D)$, is $\mathbfΣ^1_2$-complete (assuming $ \ mathrm {p} \ not = \ mathrm {np} $）。我们还进行了部分对话，例如地狱的描述性类似物-ne \ v set \ v ril定理表征了$ \mathbfς^1_2 $ - complete Graph Graph graph groph graph groph groph shoper grophismismismiss问题。我们表明，其CSP的每个可溶解borel实例都具有borel溶液的结构恰好是宽度1结构。而且，我们证明了一些界限某些有界宽度结构的投影复杂性的结果。
We adapt tools from the algebraic approach to constraint satisfaction problems to answer descriptive set theoretic questions about Borel CSPs. We show that if a structure $\mathcal D$ does not have a Taylor polymorphism, then the corresponding Borel CSP is $\mathbfΣ^1_2$-complete. In particular, by the CSP Dichotomy Theorem, if $\operatorname{CSP}(\mathcal D)$ is $\mathrm{NP}$-complete, then the Borel version, $\operatorname{csp}_B(\mathcal D)$, is $\mathbfΣ^1_2$-complete (assuming $\mathrm{P}\not=\mathrm{NP}$). We also have partial converses, such as a descriptive analogue of the Hell--Ne\v set\v ril theorem characterizing $\mathbfΣ^1_2$-complete graph homomorphism problems. We show that the structures where every solvable Borel instance of their CSP has a Borel solution are exactly the width 1 structures. And, we prove a handful of results bounding the projective complexity of certain bounded width structures.
