Complexity Theory Issues in Numeric and Algebraic Computation

数值和代数计算中的复杂性理论问题

• 批准号: 9103285
• 负责人: James Renegar
• 金额: $ 19.28万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-09-01 至 1995-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9103285&HistoricalAwards=false
• 关键词: Complexity; Theory; Issues; Numeric; Algebraic

This project concerns complexity theoretic aspects of numeric and algebraic computation. One topic is problem solving using approximate data, as occurs if the actual data must be either approximated through experimentation or rounded for computation. Attempts will be made to lay some foundations for a complexity theory which incorporates approximate data, in contrast to traditional complexity theory where exact rational data is required. Some emphasis will be given to devising efficient algorithms for solving certain problems using approximate data, most notably linear programming problems. Another topic is computational real semi-algebraic geometry, e.g., quantifier elimination methods for the first order theory of the reals. Attention will be given to a few well-known open problems in this area as well as to the common ground between it and numeric computation. This common ground is a natural place to build a general theory of condition numbers as well as to study extensions of standard problems in numeric computation such as solution approximation.

这个项目涉及数值和代数计算的复杂性理论方面。其中一个主题是使用近似数据解决问题，如果实际数据必须通过实验近似或四舍五入进行计算，则会出现这种情况。将尝试为包含近似数据的复杂性理论奠定一些基础，与需要精确有理数据的传统复杂性理论形成对比。一些重点将给予设计有效的算法来解决某些问题，使用近似数据，最显著的线性规划问题。另一个主题是计算实数半代数几何，例如，实数一阶理论的量词消去方法。我们将注意到这一领域中几个众所周知的开放问题，以及它与数值计算之间的共同点。这个共同点是建立条件数的一般理论以及研究数值计算中标准问题（如解近似）的扩展的自然场所。