RUI: Computational Complexity of Continuous Functions

RUI：连续函数的计算复杂性

• 批准号: 8712121
• 负责人: Lenore Blum
• 金额: $ 8.4万
• 依托单位: Mills College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-09-15 至 1990-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8712121&HistoricalAwards=false
• 关键词: RUI; Computational; Complexity; 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.

从历史上看，复杂性理论关注的是内在的 定义域为整数的问题的难度 或其他离散对象。 最近，人们越来越感兴趣 在理解复杂性问题的过程中， 在连续数学中。 这里，与离散情况相反， 基本的基础性问题远未解决。 下 调查是条件的作用（或对数的 （1）建立自然模型， 计算和复杂性的度量，以及（2）设计算法， 对于连续的问题。 线性规划问题及其 通过不同的模型定义的各种竞争算法， 计算和复杂性提供了丰富的思想来源， 调查