RUI: Computational Complexity of Continuous Functions

在历史上，复杂性理论一直关注问题的内在难度，这些问题的潜在领域由整数或其他离散对象组成。最近，人们对理解在解决源于连续数学的问题时产生的复杂性问题越来越感兴趣。在这里，与离散的情况相比，基本的基本问题远远没有得到解决。正在研究的是问题的条件(或条件的对数)在(1)建立自然的计算模型和复杂性度量，以及(2)为连续问题设计算法中所起的作用。线性规划问题及其各种相互竞争的算法通过不同的计算和复杂性模型定义，为本研究提供了丰富的思想来源。

Historically complexity theory has been concerned with the intrinsic difficulty of problems whose underlying domain consists of the integers or other discrete objects. More recently, there is a growing interest in understanding complexity issues arising in solving problems rooted in continuous mathematics. Here, in contrast to the discrete case, the basic foundational questions are far from resolved. Under investigation is the role the condition (or the logarithm of the condition) of a problem plays in (1) formulating natural models of computation and measures of complexity, and (2) designing algorithms, for continuous problems. The linear programming problem with its various competing algorithms defined via disparate models of computation and complexity provides a rich source of ideas for this investigation.