RUI: Computational Complexity of Continuous Functions

点击翻译按钮获取中文摘要

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.