The Foundations of Computation and Complexity Theory over the Reals or an Arbitrary Ring

实数或任意环的计算和复杂性理论基础

• 批准号: 8907663
• 负责人: Lenore Blum
• 金额: $ 6万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-09-01 至 1991-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8907663&HistoricalAwards=false
• 关键词: Foundations; Computation; Complexity; Theory; over

Classically, the theories of computation and computational complexity deal with discrete problems. On the other hand, many computational problems have the real numbers as natural domain. A variety of ad hoc methods and models have been employed to analyze complexity issues in this realm, but unlike the classical case, a natural and invariant theory has not yet emerged. This project is pursuing the foundations of a formal theory of computation and complexity over the reals, or an arbitrary ring R. It integrates classical recursive function theory and complexity theory with mainstream algebra, analysis and topology.

经典地，计算理论和计算复杂性处理离散问题。另一方面，许多计算问题以实数为自然域。各种各样的特别方法和模型被用来分析这一领域的复杂性问题，但与经典案例不同的是，一个自然不变的理论尚未出现。本课题研究的是实数或任意环r上计算和复杂性的形式理论基础，它将经典递归函数理论和复杂性理论与主流代数、分析和拓扑学相结合。