Graph Isomorphism and Constraint Satisfaction Problems

概述：计算复杂性研究是理论计算机科学中一个充满活力的研究领域，其核心问题是“计算机可以有效地解决哪些问题？”和“什么类型的算法提供这些解决方案？“在整个计算机科学中有着悠久的历史。回答这些大问题的进展通常限于分析特定类别的问题或特定算法，并且很难将一类问题的结果与另一类问题的结果联系起来。然而，Abramsky，Dawar（该项目的主管）和Wang最近的工作引入了一个令人惊讶的范畴理论结构，将两类问题联系起来，即图同构（GI）和约束满足问题（CSP）。这种结构，被称为k-pebbling comonad，还没有得到很好的理解，但代表了一个有前途的新途径，应用范畴理论的方法来复杂性理论。因此，目前的项目的目的是首先加深我们对k-pebbling comonad的理解，其次找到新的更一般的结构，这将建立GI和CSP之间的进一步联系。我们的目的是创造一些结构，这些结构将（类似于范畴论在纯数学和其他地方的应用）解开不同类别问题之间的新联系，并提出现有结果的概括。具体目标：该项目旨在增加我们对现有共同一元结构所产生的联系的理解，并创建类似的新结构。这将有助于我们更好地了解GI和CSP的最新发展以及这些领域之间的潜在联系。问题，我们将集中在最初涉及推广现有的建设，包括以下内容：-我们可以定义一个自然的类别，同态对应的多项式时间的情况下，布拉托夫的算法CSP以同样的方式，鹅卵石合作单子捕捉当地的一致性？从这个定义中，我们可以提取同构的什么算法，它们在什么类的图上工作？在另一个方向上，我们知道由pebbling co-monad定义的同构概念对应于著名的Weisfeiler-Lehman等价，我们能否构造一个自然范畴，其中同构概念对应于严格更强的等价形式，如IM-等价？这会产生什么样的同态近似？这些与CSP的算法有什么关系？我们能否将这些类别中的同构概念与巴拜GI算法的易于处理的情况联系起来？在这些框架中，困难（拟多项式）的情况是否有一个自然的解释？这些范畴中的同态对应于什么样的困难情况，这与CSP有关吗？结论：以这些问题为起点，很明显，这一研究过程既有可实现的里程碑，也有令人兴奋的发现的潜力。至少，该计划应导致更好地理解CSP和GI方法之间的共性。除此之外，如果研究导致了GI和CSP之间方法转移的一般代数/分类框架的发展，则可以认为研究是成功的。然而，这项研究的范围不会受到这一目标的限制，研究这种方法可以想象导致发现问题类别之间的一般分类转移机制，甚至如Abramsky，Dawar和Wang的论文结论中所暗示的那样，“复杂性类别的分类描述”。

Overview: The study of Computational Complexity is a vibrant area of research in Theoretical Computer Science and its central questions of "which problems in can be solved efficiently by computers?" and "what type of algorithms provide these solutions?" have a long history within Computer Science as a whole. Progress in answering these big questions is often limited to the analysis of specific classes of problems or specific algorithms and it can be difficult to relate results for one class of problem to those of another. However, recent work by Abramsky, Dawar (the supervisor of this project) and Wang introduced a surprising category theoretic construction linking two such classes of problems, namely Graph Isomorphism (GI) and Constraint Satisfaction Problems (CSP). This construction, known as the k-pebbling comonad, is as yet not very well understood but represents a promising new avenue for applying category theoretic methods to complexity theory. Thus the current project is aiming firstly to deepen our understanding of the k-pebbling comonad and secondly to find new more general constructions which will build further links between GI and CSP. Our intention is to create constructions which will (similar to the application of category theory in pure mathematics and elsewhere) unlock new connections between different classes of problems and suggest generalisations of existing results. Concrete aims:This project aims to increase our understanding of the links made by existing co-monadic constructions and to create similar new constructions. This will help us to better understand the recent developments in GI and CSP and the potential links between these areas. The questions which we will focus on initially involve generalising the existing constructions and include the following:- Can we define a natural category for which homomorphism corresponds to the polynomial-time cases of Bulatov's algorithm for CSP in the same way that the pebbling co-monad captures local consistency? From this definition, what algorithms for isomorphism can we extract, and on what classes of graphs do they work?- In the other direction, we know that the notion of isomorphism defined by the pebbling co-monad corresponds to the well-known idea of Weisfeiler-Lehman equivalence, can we construct a natural category where the notion of isomorphism corresponds to strictly stronger forms of equivalence such as IM-equivalence? What approximation to homomorphism does this yield? And, how do these relate to algorithms for CSPs?- Can we relate the notions of isomorphism in these categories to the tractable cases of Babai's algorithm for GI? Do the hard (quasipolynomial) cases have a natural interpretation in these frameworks? To what do these hard cases correpond in terms of homomorphisms in these categories and can this be related to CSP?Conclusion:With these questions as a starting point, it is clear that this course of research has both achievable milestones and potential for exciting discoveries. At a minimum, this programme should lead to a better understanding of the commonalities between methods in CSP and GI. Further to this, the research could be considered a success if it led to the development of a general algebraic/categorical framework for the transfer of methods between GI and CSP. However the scope of this research would not be limited by this goal and researching such methods could conceivably lead to the discovery of general categorical transfer mechanisms between classes of problems or even, as alluded to in the conclusion of Abramsky, Dawar & Wang's paper, "categorical descriptions of complexity classes"