Measure and Randomness in Computational Complexity

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

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.