Low-Level Complexity: Logic, Automata and Circuits

低级复杂性：逻辑、自动机和电路

• 批准号: 9207829
• 负责人: David Barrington
• 金额: $ 15.58万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-08-15 至 1996-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9207829&HistoricalAwards=false
• 关键词: Low; Level; Complexity; Logic; Automata

Recent work by the PI and others has provided a new synthesis of description of low-level complexity classes-sets of formal languages which can be recognized under tight resource bounds in various models of computation. Complexity classes originally based on uniform families of boolean circuits have been shown to have equivalent definitions using finite monoids and first-order logic. This work will apply this synthesis to the separation of low-level complexity classes (especially classes based on threshold circuits), the study of uniformity of circuit families, and the extension of the circuit model to new kinds of computation.

PI和其他人最近的工作提供了一种新的合成方法， 描述低层次复杂性类集的形式 在严格的资源限制下可以识别的语言 在不同的计算模型中。 复杂度类 最初基于布尔电路的统一族， 已被证明有等价的定义使用有限幺半群 一阶逻辑 这项工作将把这种综合应用于 低层次复杂性类的分离（特别是 基于阈值电路的类），均匀性的研究 的电路家族，和电路模型的扩展， 新的计算方式