Measure and Randomness in Computational Complexity

计算复杂性的测量和随机性

• 批准号: 9610461
• 负责人: Jack Lutz
• 金额: $ 18.34万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2000-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9610461&HistoricalAwards=false
• 关键词: Measure; Randomness; Computational; Complexity

This project investigates resource-bounded measure and its implications for central questions in computational complexity. Weak completeness will be further developed as a tool for proving intractability. Such strong hypotheses as "NP does not have p- measure 0" (already known to have numerous plausible consequences) will be studied with particular attention to their reasonableness and explanatory power. New applications of the resource-bounded probabilistic method will be sought, and relationships among randomized complexity, circuit-size complexity, natural proofs, and one-way functions will be carefully examined. The underlying theory of resource-bounded measure will be extended in order to apply it to a wider variety of problems and probability measures. This will include a systematic study of efficient martingales and transformations of martingales. Applications of the extended theory to algorithmic information, computational depth, machine learning and prediction, real-and complex-valued computation, and the computation of higher-type functionals will be investigated.

本计画探讨资源限制测度及其对计算复杂性中心问题的意涵。 弱完备性将进一步发展为证明难处理性的工具。 像“NP不具有p-测度0”这样的强假设（已经知道有许多可能的结果）将被研究，特别注意它们的合理性和解释力。 资源有限的概率方法的新应用将寻求，随机复杂性，电路大小的复杂性，自然的证据，和单向函数之间的关系将仔细检查。 资源有限测度的基本理论将得到扩展，以便将其应用于更广泛的问题和概率测度。 这将包括有效鞅和鞅变换的系统研究。 将研究扩展理论在算法信息、计算深度、机器学习和预测、实值和复值计算以及高阶泛函计算中的应用。