"Algebraic and logical approaches to circuit complexity"

“电路复杂性的代数和逻辑方法”

• 批准号: 8902369
• 负责人: Howard Straubing
• 金额: $ 9.41万
• 依托单位: Boston College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-01 至 1992-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8902369&HistoricalAwards=false
• 关键词: Algebraic; logical; approaches; circuit; complexity

The project examines the structure of classes of problems solvable by constant-depth families of circuits biult from unbounded fan-in gates of various descriptions. All of the classes under consideration are contained in the complexity class NC1, which is a model for the family of problems solvable by very fast parallel algorithms. The principal goal of the research is to answer a number of open questions concerning the inclusions among these classes; in particular, to settle the question of wheather either iterated addition mod m or the majority problem is complete for NC1 with respect to constant-depth reductions. This work will employ the recently discovered characterization of NC1 and its subclasses in terms of formal logic and finite automata. These characterizations make it possible to apply model-theoretic and algebraic methods to the study of circuit complexity. It is hoped that, in addition to settling these immediate questions, a new methodology for proving lower bounds in computational complexity will result, and that this will be of benefit in studying classes of higher complexity.

该项目研究了可解决的问题类的结构， 由无界扇入门生成的常深度电路族 各种各样的描述 考虑中的所有类都是 包含在复杂性类NC 1中，这是家族的模型 可以通过非常快速的并行算法解决的问题。 校长 这项研究的目的是回答一些悬而未决的问题， 这些类别之间的包容性;特别是，解决 是模m的迭代加法还是多数的问题 问题是完整的NC 1相对于恒定的深度减少。 这项工作将采用最近发现的NC 1的特性 及其子类的形式逻辑和有限自动机。 这些 表征使得可以应用模型理论和 研究电路复杂性的代数方法。 希望 除了解决这些紧迫的问题，一个新的 证明计算复杂性下限的方法将 结果，这将有利于学习更高的班级， 复杂性