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.