Complexity Theory Issues in Numeric and Algebraic Computation

这个项目涉及数值和代数计算的复杂性理论方面。一个主题是使用近似数据解决问题，如果实际数据必须通过实验进行近似或四舍五入进行计算，就会发生这种情况。与需要精确理性数据的传统复杂性理论不同，我们将试图为包含近似数据的复杂性理论奠定一些基础。部分重点将放在设计有效的算法，以解决某些问题使用近似数据，最明显的线性规划问题。另一个主题是计算实半代数几何，例如实数的一阶理论的量词消去法。我们将关注这一领域的几个著名的公开问题，以及它与数值计算之间的共同点。这种共同点是建立条件数的一般理论以及研究数值计算中标准问题的扩展(如解近似)的自然场所。

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.