Circuits, Logic and Symmetry

无论是在计算机科学中还是在更广泛的科学中，P与NP猜想都可以说是最严重的问题之一。这个猜想关注的是解决问题本身的行为，询问我们认为难以解决的问题是否真的很难解决，或者他们是否接受了一些聪明的、高效的可计算的解决方案。从技术上讲，我们能把NP和P分开吗？NP是一类包含被认为是困难的问题，而P是一类有效可解的问题。为了取得进展，我们需要对这个问题有一些了解，这样才能有效地解决这个问题。换句话说，我们需要对P进行“良好”的描述。这是一个挑战，因为复杂类是使用低级机器模型定义的。这些模型很难分析，也让我们很难洞察班级的性质。一种方法是使用逻辑学开发复杂类的替代特征，我们认为逻辑学是抽象的高级语言，而不是低级机器模型。这些逻辑处理数据的抽象表示，而不是二进制字符串，并且至关重要的是，它们尊重表示中固有的对称性。这些逻辑特征提供了很好的洞察力，以了解需要哪些“抽象机械”(例如，递归、计数操作等)来准确地解决复杂类中的那些问题。现在我们可以更具体地框架我们前面的问题：是否存在表征P的逻辑？这个问题不仅与P与NP猜想密切相关，而且本身是一个关于抽象性质的深层次问题。为了取得进展，我们想要了解高级、抽象语言的计算能力与低级机器的计算能力的区别。最近的研究表明，高级程序定义的算法具有很强的对称性。相比之下，机器模型给出的算法具有一个非常弱的对称性条件。因此，这些模型之间的关系，以及这一领域的中心问题，可以归结为关于对称条件的意义的问题。事实上，最近的结果使我们能够提出关于对称性作用的细粒度问题，使我们能够使用对称性所需的渐进弱化来在高级语言和低级模型之间进行内插。所提出的工作通过探索对称性在每种情况下如何在分析复杂性中发挥作用，将复杂性理论中的三种基本方法联系在一起。它们是电路复杂性、描述复杂性和证明复杂性。

The P vs NP conjecture is arguably one of the deepestproblems both in computer science and in science more generally. The conjectureconcerns the very act of problem solving itself, asking if the problems we thinkare hard to solve are in fact hard, or if they admit some clever, efficientlycomputable, solution. Put more technically, can we separate NP, a classcontaining problems believed to be hard, from P, the class of efficientlysolvable problems. In order to make progress we need some understanding of whatit is about a problem that makes it efficiently solvable. In other words, weneed a `nice' characterization of P. This is a challenge because complexityclasses are defined using low-level machine models. These models are hard toanalyse and offer us little insight into the nature of the class. One approachhas been to develop alternative characterizations of complexity classes usinglogics, which we think of as abstract high-level languages, rather thanlow-level machine models. These logics work over abstract representations ofdata, rather than binary strings and, crucially, respect the symmetries inherentin that representation. These logical characterizations offer great insight intowhat pieces of `abstract machinery' (e.g. recursion, counting operations, etc.)are required to solve exactly those problems in a complexity class. We can nowframe our previous question more concretely: Is there a logic that characterizesP?This question is not only closeely related to the P vs NP conjecture, butis itself a deep question about the nature of abstraction. In order to makeprogress we would like to understand what differentiates the computational powerof high-level, abstract languages from that of low-level machines. Recent workhas shown that high-level programs define algorithms with a strong symmetryproperty. In contrast, algorithms given by machine models are characterized by avery weak symmetry condition. It follows that the relationship between thesemodels, and hence the central question of this field, can be reduced to aquestion about the significance of the symmetry condition. In fact, recentresults have enabled us to ask fine-grained questions about the role ofsymmetry, allowing us to use progressive weakenings of the symmetry requirementin order to interpolate between the high-level languages and low-levelmodels.The proposed work connects three fundamental approaches in complexitytheory, by exploring how symmetry plays a role in analysing complexityin each case. They are circuit complexity, descriptive complexity andproof complexity.