Circuit Complexity: Grid Graphs, Planar Circuits, and Lower Bounds

电路复杂性：网格图、平面电路和下限David Mix Barrington马萨诸塞大学计算机科学系项目说明复杂性理论是对计算问题所需资源的数学研究。在电路复杂性理论中，这些资源是解决问题的布尔电路族的大小、深度和其他参数。基本结果是上界(在满足一定资源约束的情况下解决问题的算法)和下界(证明没有这样的算法可以做到这一点)。基本对象是复杂性类，它是在一定的资源约束下可以解决的一组问题。对于大多数自然和健壮的约束选择，结果类都有完整的问题-其解决方案需要一种基本的算法技术，足以解决类中的所有问题。完全问题的上界和下界然后给出关于这类问题的结果。这个项目研究了两个具体的计算问题：网格图可达性和单调平面电路值。给出一个嵌入在矩形网格上的图和两个节点，是否存在从一个节点到另一个节点的路径？给定的AND和OR门电路(其中没有导线交叉)和给定输入计算出的值是多少？在每一种情况下，PI和其他人最近的工作都改进了问题版本的上界。这里的目标是改进这些算法结果，探索各种版本，将它们彼此联系起来，并与标准问题联系起来。这一探索将在PI和其他人在定性复杂性理论方面的先前工作的背景下进行。这项工作确定了一组在各种模型上都是健壮的标准复杂性类，并根据用一阶逻辑表达问题所需的句法资源来描述这些类的特征，此外，进一步的工作将应用该逻辑框架来研究低复杂度的下界问题。这一领域的突出问题已经持续了十年，它要证明某些自然问题不在电路类之外，例如$Acc^0$。在这里，PI和其他人在最近的工作中开发的两种新方法提供了一些希望：计数电路类和中等水平的一致性。

AbstractCircuit Complexity: Grid Graphs, Planar Circuits, and Lower BoundsDavid Mix BarringtonComputer Science DepartmentUniversity of MassachusettsProject DescriptionComplexity theory is the mathematical study of the resources needed for computational problems. In circuit complexity theory these resources are the size, depth, and other parameters of boolean circuit families that solve the problems. The basic results are upper bounds (algorithms solving the problem while obeying certain resource constraints) and lower bounds (proofs that no such algorithm can do so).This project takes a qualitative approach to circuit complexity. The basic object is a complexity class, which is the set of problems that can be solved within certain resource constraints. For most natural and robust choices of constraints, the resulting class has complete problems --- problems whose solution requires a fundamental algorithmic technique that suffices to solve all the problems in the class. Upper and lower bounds for the complete problems then give us results about the classes. This project studies two specific computational problems: grid graph reachability and monotone planar circuit value. Given a graph embedded on a rectangular mesh, and two nodes, is there a path from one node to the other? What is the value computed by a given circuit of AND and OR gates, where no wires cross, and a given input? In each case recent work of the PI and others have improved upper bounds for versions of the problem. The goal here is to improve these algorithmic results and explore the various versions, relating them to each other and to standard problems. This exploration will be carried out in the context of prior work by the PI and others in qualitative complexity theory. This work has identified a set of standard complexity classes that are robust across a variety of models, and developed a single framework characterizing these classes in term of the syntactic resources needed to express their problems in first-order logic.In addition, further work will apply the logical framework to lower bound problems in low-level complexity. The outstanding problem in this area, open for a decade, is to prove some natural problem to be outside of a circuit class such as $ACC^0$. Here two new approaches, developed in recent work of the PI and others, offer some hope: counting circuit classes and intermediate levels of uniformity.