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.

电路复杂度：网格图、平面电路和下界David Mix Barrington计算机科学系马萨诸塞大学项目描述复杂性理论是对计算问题所需资源的数学研究。 在电路复杂性理论中，这些资源是解决问题的布尔电路族的大小，深度和其他参数。 基本结果是上界（算法在遵守某些资源约束的情况下解决问题）和下界（证明没有这样的算法可以做到这一点）。 基本对象是一个复杂性类，这是一组可以在一定的资源约束下解决的问题。 对于大多数自然和鲁棒的约束选择，产生的类有完整的问题-问题的解决需要一个基本的算法技术，足以解决类中的所有问题。 上界和下界的完整的问题，然后给我们的结果的类。本计画研究两个特定的计算问题：网格图可达性与单调平面回路值。给定一个嵌入在矩形网格上的图，有两个节点，是否存在从一个节点到另一个节点的路径？ 在没有导线交叉的情况下，给定输入，由与门和或门组成的给定电路计算出的值是多少？在每一种情况下，PI和其他人最近的工作都提高了问题版本的上限。 这里的目标是改进这些算法结果并探索各种版本，将它们彼此关联并与标准问题关联起来。 这种探索将在PI和其他定性复杂性理论的先前工作的背景下进行。 这项工作已经确定了一套标准的复杂性类，是强大的各种模型，并制定了一个单一的框架，这些类的语法资源来表达他们的问题在一阶logic.In，进一步的工作将适用于低层次复杂性的下限问题的逻辑框架。 这一领域的突出问题是证明某些自然问题不属于电路类，如ACC ^0 $。在这里，PI和其他人最近的工作中开发的两种新方法提供了一些希望：计数电路类和均匀性的中间水平。