Low-Level Complexity: Logic, Automata, and Circuits

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

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

Many of the principal aims of complexity theory are served by an examination of the problems solvable by abstract computers under tight resource bounds. Research will be continued on such complexity classes as L (those problems solvable with memory proportional to the logarithm of the input size) and NC1 (those problems solvable by Boolean circuits of polynomial size and logarithmic depth). In particular, the ramifications of recent work on branching programs and non-uniform finite automata will be explored.

复杂性理论的许多主要目标都是通过检查抽象计算机在严格的资源限制下可解决的问题来实现的。 将继续研究 L（可通过与输入大小的对数成比例的内存来解决的问题）和 NC1（可通过多项式大小和对数深度的布尔电路解决的问题）等复杂性类别。 特别是，将探讨最近关于分支程序和非均匀有限自动机的工作的影响。