Information-Based Complexity of Multivariate Problems

多元问题的基于信息的复杂性

• 批准号: 0095709
• 负责人: Grzegorz Wasilkowski
• 金额: $ 25.52万
• 依托单位: University of Kentucky Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-06-01 至 2005-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0095709&HistoricalAwards=false
• 关键词: Information; Based; Complexity; Multivariate; Problems

Many multivariate problems of practical interests are intractable in the worst case setting. Such intractability could be removed by either identifying new properties (i.e., classes) that allow for efficient algorithms or by switching to the average (or probabilistic) settings. This is often referred to as breaking intractability. A substantial part of the proposed research will deal with breaking intractability of a number of important problems. This will lead to deeper knowledge of the complexities of multivariate problems and will result in new efficient algorithms for a host of important problems. Related to the average case study are path integrals. The research will be a continuation of a recently initiated study on the complexity of path integration and will provide additional complexity bounds and new efficient algorithms. A number of important problems deal with classes of functions of unbounded domains. However, there are but few corresponding complexity results and, in practice, commonly used algorithms are ad hoc and are not optimal. Significant part of the proposed research will deal with problems defined for classes of functions with unbounded domains; both the worst case and the average case settings will be studied. This will enrich understanding of the complexity of such problems and will provide new algorithms that are optimal (or almost optimal). The theoretical work will yield new and efficient algorithms for a host of important problems. These algorithms will be developed and thoroughly tested. Graduate students will be involved in both theoretical and development phases of the research.

许多实际利益的多元问题在最坏情况下是难以解决的。这种棘手性可以通过识别新的特性（即，类），允许有效的算法或通过切换到平均（或概率）设置。这通常被称为打破棘手。 拟议研究的一个重要部分将涉及打破一些重要问题的棘手性。这将导致更深入地了解多元问题的复杂性，并将导致新的有效算法的主机的重要问题。与平均案例研究相关的是路径积分。 这项研究将是最近发起的路径集成的复杂性研究的延续，并将提供额外的复杂性界限和新的高效算法。一些重要的问题涉及无界域的函数类。然而，有，但很少有相应的复杂性的结果，在实践中，常用的算法是特设的，并不是最佳的。重要的一部分，拟议的研究将处理定义的函数类与无界域的问题，最坏的情况下和平均情况下的设置将进行研究。这将丰富对这些问题的复杂性的理解，并将提供新的算法是最佳的（或几乎最佳的）。理论工作将产生新的和有效的算法的主机的重要问题。这些算法将被开发和彻底测试。研究生将参与研究的理论和发展阶段。