PYI: Structural Complexity Theory

PYI：结构复杂性理论

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

The structure of feasible computations will determine whether we can efficiently solve the optimization problems posed by nature and the modern world. The project investigates which problems have efficient solutions, and why some problems lack computationally feasible algorithms. Of particular interest are the structural relationships between complexity classes, and the internal structure of complexity classes. A long-term goal is to show that the "structural" approach to computational complexity is a broadly applicable paradigm of research, and a companion to algorithms. Structural approaches to many areas (including real-valued computation and zero-knowledge theory) will be pursued, and many themes of structural complexity theory (including lowness, positive reductions, ranking, and the isomorphism conjecture) will be re-examined.

可行计算的结构将决定我们是否可以有效地解决自然界和现代世界所带来的优化问题。 该项目调查了哪些问题具有有效的解决方案，以及为什么一些问题缺乏计算可行的算法。 特别有趣的是复杂性类别与复杂性类别的内部结构之间的结构关系。 一个长期的目标是表明计算复杂性的“结构”方法是广泛适用的研究范式，并且是算法的伴侣。 将探讨许多领域的结构方法（包括真实评估的计算和零知识理论），并将重新审查结构复杂性理论的许多主题（包括Lowness，Lowness，积极的降低，排名和同构猜想）。