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.

可行计算的结构将决定我们能否有效地解决自然界和现代世界提出的优化问题。该项目调查了哪些问题有有效的解决方案，以及为什么有些问题缺乏计算上可行的算法。特别有趣的是复杂性类之间的结构关系，以及复杂性类的内部结构。长期目标是表明计算复杂性的“结构”方法是一种广泛适用的研究范式，是算法的伴侣。许多领域的结构方法（包括实值计算和零知识理论）将被追求，结构复杂性理论的许多主题（包括低，正约简，排序和同构猜想）将被重新审视。