Average Case and Probabilistic Setting of Information-Based Complexity

基于信息的复杂性的平均情况和概率设置

• 批准号: 9420543
• 负责人: Joseph Traub
• 金额: $ 42.12万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-06-15 至 1999-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9420543&HistoricalAwards=false
• 关键词: Average; Case; Probabilistic; Setting; Information

Problems with only partial or contaminated information arise in many disciplines: computer science, physics and chemistry, control theory, statistics, prediction and estimation, scientific and engineering computation, geophysics, decision theory, and finance. Furthermore, this information is often expensive to obtain. The goal of information-based complexity is to create a computational complexity theory for problems with partial, contaminated, and priced information, and to apply the results to solving specific problems in varied disciplines. The prime foci of this project are the following: (1) Breaking Intractability: Many problems in science, engineering, and even finance, deal with functions that have a large number, d, of variables. However, typical multivariate problems are intractable in the worst case deterministic setting. The only way to break intractability is to weaken the assurance by switching to another setting. Randomized, average case, and probabilistic settings continue to be studied. In particular, it has been proven that multivariate integration and approximation are both strongly tractable on the average. The proof is non- constructive; the problem of how to sample in d dimensions to achieve strong tractability is being addressed. (2) Software Development and Testing: Theoretical investigations have led to algorithms for important problems such as high dimensional integration. To make these methods widely available, software is being developed and tested. Since these methods contain a large amount of inherent parallelism, the implementation is being done on a workstation network. Testing is also planned on parallel computers. Real-world problems are used for testing. (3) Probabilistic Complexity of Piece-Wise Smooth Functions: Piece-wise smooth functions arise in diverse areas of science and technology such as computer vision, image and signal processing, scientific computation, meteorology, seismology, and to mography. Because of negative results of the worst-case setting these problems are being studied in the probabilistic setting. New algorithms for integration, approximation, and detection of singular points are being studied and implemented.

只有部分或污染信息的问题出现在许多学科中：计算机科学、物理和化学、控制理论、统计学、预测和估计、科学和工程计算、地球物理、决策理论和金融。此外，获取这些信息的成本往往很高。基于信息的复杂性的目标是为部分、污染和定价信息的问题创建一个计算复杂性理论，并将结果应用于解决不同学科的具体问题。这个项目的主要焦点是：(1)打破难治性：科学、工程甚至金融中的许多问题都涉及具有大量变量的函数。然而，典型的多变量问题在最坏情况下是难以解决的。打破顽固的唯一方法是通过切换到另一个设置来削弱保证。继续研究随机、平均情况和概率设置。特别是，多元积分和近似在平均上都具有很强的可处理性。证明是非建设性的；如何在d维上采样以达到强可追溯性的问题正在被解决。(2)软件开发和测试：理论研究导致了高维积分等重要问题的算法。为了使这些方法广泛使用，正在开发和测试软件。由于这些方法包含大量固有的并行性，因此在工作站网络上完成实现。测试也计划在并行计算机上进行。实际问题用于测试。(3)分段平滑函数的概率复杂性：分段平滑函数出现在计算机视觉、图像和信号处理、科学计算、气象学、地震学和地学等不同的科学技术领域。由于最坏情况下的结果是负的，这些问题是在概率情况下研究的。新的算法的积分，逼近，和检测奇异点正在研究和实施。