Fractal Geometry in Complexity Classes

点击翻译按钮获取中文摘要

Fractal-geometric aspects of complexity classes and central questions in computational complexity will be studied using resource-bounded dimension, refining the resource-bounded measure approach. Specific topics include:Polynomial-time dimension will be used to understand the fractal geometry of NP and other complexity classes, with an emphasis on the self-similarity between a complexity class and its complete sets. Hypotheses such as "NP has positive p-dimension" that imply only average-case hardness will be compared to resource-bounded measure hypotheses and investigated for their consequences in computational complexity.Zero-one laws for the resource-bounded dimensions of complexity classes will be investigated unconditionally and under derandomization assumptions.The contrasting behavior of polynomial-time reductions in different orders of scaled dimension will be further studied to yield new insight into completeness phenomena and the failure of the random oracle hypothesis.Moving beyond limitations of the martingale approach, compressibility will be employed to develop resource-bounded measure and dimension in small complexity classes.The proposed research also includes some related investigations that go beyond computational complexity:The equivalence of dimension and log-loss prediction will be used to apply .nite-state dimension to universal prediction. Relationships between VC-dimension and fractal dimension will be developed and applied in computational learning theory.Correspondence principles for constructive dimension and Hausdor. dimension will be developed to provide a new Kolmogorov-complexity method to simplify proofs and establish new results in classical fractal geometry.Intellectual merit: As evidenced by its online bibliography, resource-bounded measure has been a central approach to computational complexity with over 100 papers by 60 authors during the past 15 years. The proposed research is a challenging program that refines this approach using resource-bounded dimension. This will yield further quantitative insight into the structure of complexity classes, new understanding of the limitations of resource-bounded measure, and better assessment of the reasonableness of resource-bounded measure hypotheses.Broader impacts: This research will also establish new links between computational complexity, information theory, learning theory, and fractal geometry, with the expected long-term effect of increasing interdisciplinary interaction among those fields. Concepts and ideas from previously distinct areas will be applied through the unifying concept of resource-bounded dimension to yield new ways of thinking. The research results will be made widely available as technical reports and conference publications. Online bibliographies of all relevant papers will be maintained to help researchers with better access to the literature. Graduate students from underrepresented groups will play a significant role in the project.