论文标题
在约束满意度和结构同构方面的同时学
Cohomology in Constraint Satisfaction and Structure Isomorphism
论文作者
论文摘要
约束满意度（CSP）和结构同构（SI）是计算机科学中最精心研究的计算问题之一。虽然认为这两个问题都不是在$ \ texttt {ptime}中，但在$ \ texttt {ptime} $近似两个问题上都完成了很多工作。两个这样的历史上重要的近似值是CSP的$ K $ - 一致性算法和SI的$ K $ - Weisfeiler-Leman算法，这两种算法都是基于传播本地部分解决方案的。这些算法的局限性是众所周知的。 $ k $ - 一致性可以精确地解决有界宽度的CSP和$ k $ -Weisfeiler-Leman只能区分$ C^k $可定义的属性的结构。在本文中，我们为CSP和SI及其近似介绍了一种新颖的融化理论方法。我们表明，这两个问题都可以看作是确定前置的全局部分的存在，$ \ nathcal {h} _k（a，b）$和$ \ nathcal {i} _k（a，b）$，以及$ k $ - consisistency和$ k $ - $ k $ -weisfeiler-leman ables coptim compus的成功，这些都与这些相关性相关的效果与这些相关性相关性。此外，基于艾布拉姆斯基和其他人在量子基础上的工作，我们展示了如何在$ \ natcal {h} _k（a，b）$和$ \ nathcal {i} _k（a，a，b）中使用čechcoomology在$ \ mathcal {h} _k（a，b）_k（a，b）$（a，b）$中，以检测到所需的全球范围和衍生的$ fortive $ - $ k $ -Weisfeiler-Leman。我们表明，共同体$ k $ - 一致性可以在所有有限环上求解方程系统，并且共同体weisfeiler-leman可以在几个重要类别的结构上区分Cai-fürer-immerman财产的正面和负面实例。
Constraint satisfaction (CSP) and structure isomorphism (SI) are among the most well-studied computational problems in Computer Science. While neither problem is thought to be in $\texttt{PTIME},$ much work is done on $\texttt{PTIME}$ approximations to both problems. Two such historically important approximations are the $k$-consistency algorithm for CSP and the $k$-Weisfeiler-Leman algorithm for SI, both of which are based on propagating local partial solutions. The limitations of these algorithms are well-known; $k$-consistency can solve precisely those CSPs of bounded width and $k$-Weisfeiler-Leman can only distinguish structures which differ on properties definable in $C^k$. In this paper, we introduce a novel sheaf-theoretic approach to CSP and SI and their approximations. We show that both problems can be viewed as deciding the existence of global sections of presheaves, $\mathcal{H}_k(A,B)$ and $\mathcal{I}_k(A,B)$ and that the success of the $k$-consistency and $k$-Weisfeiler-Leman algorithms correspond to the existence of certain efficiently computable subpresheaves of these. Furthermore, building on work of Abramsky and others in quantum foundations, we show how to use Čech cohomology in $\mathcal{H}_k(A,B)$ and $\mathcal{I}_k(A,B)$ to detect obstructions to the existence of the desired global sections and derive new efficient cohomological algorithms extending $k$-consistency and $k$-Weisfeiler-Leman. We show that cohomological $k$-consistency can solve systems of equations over all finite rings and that cohomological Weisfeiler-Leman can distinguish positive and negative instances of the Cai-Fürer-Immerman property over several important classes of structures.
