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（那些由多项式大小和对数深度的布尔电路可解决的问题）这样的复杂性类。特别是，最近的分支程序和非一致有限自动机工作的分支将被探索。