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.

可行计算的结构将决定我们是否能够 有效地解决了自然界和自然界提出的优化问题， 现代世界 该项目调查了哪些问题具有有效性 解决方案，以及为什么有些问题缺乏计算可行性 算法 特别感兴趣的是结构关系 以及复杂性的内部结构 班 一个长期目标是表明，“结构性”的方法， 计算复杂性是一种广泛适用的研究范例， and a companion同伴to algorithms算法. 对许多领域采取结构性办法 （包括实值计算和零知识理论）将是 追求，和许多主题的结构复杂性理论（包括 低，积极的减少，排名，和同构猜想） 将被重新审查。