Complexity of Small-Depth Circuits

小深度电路的复杂性

• 批准号: 9203208
• 负责人: Howard Straubing
• 金额: $ 12.07万
• 依托单位: Boston College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1996-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9203208&HistoricalAwards=false
• 关键词: Complexity; Small; Depth; Circuits

The proposed research is part of a continuing study of the computational complexity of boolean circuits and related models of computation, such as threshold circuits and branching programs. All the problems to be investigated concern the manner in which the size, depth and type of gates in a circuit affect its computational power. The focus is on circuit whose depth is small (either independent of input length or logarithmic in input length) and whose size is either bounded by a polynomial in the input length or is slightly larger. The principal goal is to prove that certain problems cannot be solved under such size and depth restrictions, and thereby determine the structure of complexity classes defined by small-depth circuit families. These questions will be investigated by two distinct methods: The first is the representation of the behavior of the circuit or the program by polynomials or similar algebraic objects, and the use of Fourier analysis to discover properties of these representations. The second is the representation of a circuit's behavior as a program over a finite monoid, which permits the application of methods from the global structure theory of finite semigroups.

拟议的研究是一项持续研究的一部分， 布尔电路的计算复杂性和相关的 计算模型，如阈值电路和 分支程序 所有有待调查的问题 涉及门的尺寸、深度和类型的方式 影响其计算能力。 重点是深度较小的电路（ 与输入长度无关或输入长度为对数） 并且其大小由输入中的多项式限定 长度或稍大。 主要目的是证明 在这样的规模下，某些问题是无法解决的， 深度限制，从而决定了 由小深度电路族定义的复杂性类。 这些问题将由两个不同的专家进行调查。 方法：第一个是行为的表示， 电路或程序的多项式或类似的代数 物体，并使用傅立叶分析来发现 这些表征的性质。 二是 一个电路的行为表示为一个程序在一个 有限幺半群，它允许应用的方法，从 有限半群的整体结构理论。