Circuits, Logic and Symmetry

点击翻译按钮获取中文摘要

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.