权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Theory and Applications of Information-Based Complexity

基于信息的复杂性理论与应用

基本信息

批准号：
9731858
负责人：
Joseph Traub
金额：
$ 29.97万
依托单位：
Columbia University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
1998
资助国家：
美国
起止时间：
1998-06-01 至 2001-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9731858&HistoricalAwards=false
关键词：
Theory Applications Information Based Complexity

项目摘要

This project addresses three areas of research in information- based complexity:Theory, Applications, Software. THEORY: A major theme is the study of the computational complexity of multivariate problems in a large number of variables. In particular, the computational complexity of path integrals, that is, integrals in an infinite number of variables, will be studied. Often high dimensional multivariate problems are intractable in the worst case deterministic setting. The research emphasis will be on conditions which yield tractability and strong tractability in various settings. A second research area is to explain why low-discrepancy sequences are excellent for computing the high dimensional integrals (often, the dimensionality is in the hundreds) of mathematical finance. This belief is based on extensive software testing but there is no satisfactory theoretical explanation. The goal is to characterize very high dimensional integrals for which low-discrepancy sequences are superior to Monte Carlo. A third area is to continue research on the computational complexity of implementation testing for continuous problems. APPLICATIONS: The theory will be applied to a number of application areas, including computational complexity and new algorithms for combinatorial circuit verification. SOFTWARE: The FINDER software library contains modifications of low-discrepancy sequences. FINDER has been made available to researchers in various disciplines. Further improvements, tests, and dissemination of FINDER are planned.

本计画针对资讯复杂性的三个研究领域：理论、应用、软体. 理论：一个主要的主题是研究在大量变量的多变量问题的计算复杂性。特别是，路径积分的计算复杂性，即在无穷多个变量的积分，将进行研究。通常高维多变量问题在最坏情况下的确定性设置是棘手的。研究的重点将是在各种环境中产生易处理性和强易处理性的条件。第二个研究领域是解释为什么低差异序列非常适合计算数学金融的高维积分（通常，维数是数百）。这种信念是基于广泛的软件测试，但没有令人满意的理论解释。我们的目标是表征非常高维的积分，低差异序列是上级蒙特卡罗。第三个领域是继续研究连续问题的实现测试的计算复杂性。应用领域：该理论将被应用到许多应用领域，包括计算复杂性和组合电路验证的新算法。软件：FINDER软件库包含低差异序列的修改。 FINDER已提供给各学科的研究人员。计划进一步改进、测试和推广FINDER。