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

电路复杂性：网格图、平面电路和下界

• 批准号: 9988260
• 负责人: David Barrington
• 金额: $ 21.28万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988260&HistoricalAwards=false
• 关键词: Circuit; Complexity; Grid; Graphs; Planar

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.

摘要电路复杂性：网格图、平面电路和下界大卫·米克斯·巴林顿马萨诸塞大学计算机科学系项目描述复杂性理论是对计算问题所需资源的数学研究。 在电路复杂性理论中，这些资源是解决问题的布尔电路族的大小、深度和其他参数。 基本结果是上限（在遵守某些资源限制的情况下解决问题的算法）和下限（证明没有这样的算法可以做到这一点）。该项目对电路复杂性采用定性方法。 基本对象是复杂度类，它是在一定资源限制下可以解决的问题集。 对于最自然和稳健的约束选择，生成的类具有完整的问题——其解决方案需要足以解决类中所有问题的基本算法技术。 完整问题的上限和下限然后为我们提供有关类别的结果。该项目研究两个具体的计算问题：网格图可达性和单调平面电路值。给定嵌入在矩形网格上的图和两个节点，是否存在从一个节点到另一个节点的路径？ 给定的与门和或门电路（没有电线交叉）和给定输入计算出的值是多少？在每种情况下，PI 和其他人最近的工作都改进了问题版本的上限。 这里的目标是改进这些算法结果并探索各种版本，将它们相互关联并与标准问题关联。 这一探索将在 PI 和其他人在定性复杂性理论方面的先前工作的背景下进行。 这项工作确定了一组在各种模型中都具有鲁棒性的标准复杂性类，并开发了一个单一框架，根据以一阶逻辑表达其问题所需的句法资源来表征这些类。此外，进一步的工作将将逻辑框架应用于低级复杂性的下限问题。 这个领域开放十年的突出问题是证明一些自然问题不属于电路类，例如 $ACC^0$。 PI 和其他人在最近的工作中开发的两种新方法提供了一些希望：计算电路类别和中间一致性水平。