Low-Level Complexity: Logic, Automata, and Circuits

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

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

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

复杂性类最初基于布尔的统一族 电路已被证明有等效的定义，使用有限 monoid和一阶逻辑。 该领域的研究提供了一个 低层次复杂性类的描述的新合成- 在严格的资源限制下可以识别的形式语言， 各种计算模型。 本项目将应用这种综合 到低层次复杂性类的分离， 电路族的一致性和电路模型的扩展 新的计算方式。