Structural Complexity Theory

结构复杂性理论

• 批准号: 9322513
• 负责人: Lane Hemaspaandra
• 金额: $ 15.93万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-01 至 1998-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9322513&HistoricalAwards=false
• 关键词: Structural; Complexity; Theory

The structure of feasible computations determines whether one can efficiently solve the optimization problems posed by nature and the modern world. The long-term goal of this research is to understand which problems have efficient solutions, via learning why certain problems may lack computationally feasible algorithms. Of particular interest are the structural relationships between complexity classes, and the internal structure of complexity classes. Though the project intends to broadly investigate this area, focus will be given to the research via two themes: (a) dealing with unpredictable execution order; and (b) the properties of sparse sets. On the first topic, this project investigates the class of languages computable via a large number of short subtasks, each of which is given the (small) result of the subtask that executed before it. This has been studied by Cai and Furst and others for the case where the scheduling of the subtasks is trivial and fixed. However, the project studies the case in which the order in which the subtasks execute is unpredictable. On the second topic, several issues dealing with sparse sets (which are a classic examples of `sets of low information content`) are examined.

可行计算的结构决定了能否有效地解决自然和现代世界提出的优化问题。 这项研究的长期目标是通过了解为什么某些问题可能缺乏计算上可行的算法来了解哪些问题有有效的解决方案。 特别令人感兴趣的是复杂性类别之间的结构关系以及复杂性类别的内部结构。 尽管该项目打算广泛研究这一领域，但研究重点将集中在两个主题上：(a) 处理不可预测的执行顺序； (b) 稀疏集的性质。 关于第一个主题，该项目研究了可通过大量短子任务计算的语言类别，每个子任务都会给出在其之前执行的子任务的（小）结果。 Cai 和 Furst 等人针对子任务调度简单且固定的情况进行了研究。 然而，该项目研究了子任务执行顺序不可预测的情况。 在第二个主题上，研究了处理稀疏集（这是“低信息内容集”的经典示例）的几个问题。