Measure and Randomness in 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.