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

电路复杂性：网格图、平面电路和下界麻省大学计算机科学系david Mix barrington项目描述复杂性理论是计算问题所需资源的数学研究。在电路复杂性理论中，这些资源是解决问题的布尔电路族的大小、深度和其他参数。基本的结果是上界（算法在遵守某些资源约束的情况下解决问题）和下界（证明没有这样的算法可以这样做）。本项目采用定性方法来分析电路的复杂性。基本对象是一个复杂性类，它是在一定的资源约束下可以解决的一组问题。对于大多数自然和健壮的约束选择，生成的类具有完整的问题——解决这些问题需要一种足以解决类中所有问题的基本算法技术。完整问题的上界和下界给出了关于该类的结果。本课题研究两个具体的计算问题：网格图可达性和单调平面电路值。给定一个嵌入在矩形网格上的图，有两个节点，是否存在从一个节点到另一个节点的路径？在没有导线交叉的情况下，给定输入的与或门电路计算出的值是多少？在每种情况下，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.