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.