Fractal Geometry in Complexity Classes

复杂性类的分形几何方面和计算复杂性的中心问题将使用资源有界维度进行研究，改进资源有界度量方法。将使用多项式时间维度来理解NP和其他复杂性类的分形几何，重点是复杂性类与其完备集之间的自相似性。假设，如“NP具有正p维”，意味着只有平均情况下的硬度将与资源有限的测量假设进行比较，并研究其在计算复杂性方面的后果。在非随机化假设下，无条件地研究了复杂性类的资源有限维的零- 1定律。我们将进一步研究不同尺度维数下多项式时间约简的对比行为，从而对完备性现象和随机预言假设的失效产生新的见解。超越鞅方法的限制，可压缩性将被用于开发小复杂性类中的资源受限度量和维度。提出的研究还包括一些超越计算复杂性的相关研究：将使用维度等效和对数损失预测。niti -state维度到普遍预测。vc维数和分形维数之间的关系将在计算学习理论中得到发展和应用。构维与豪斯多的对应原则。维将发展提供一个新的kolmogorov复杂度方法来简化证明和建立新的结果在经典分形几何。知识价值：正如其在线参考书目所证明的那样，在过去的15年中，60位作者发表了100多篇论文，资源边界度量已经成为计算复杂性的核心方法。提出的研究是一个具有挑战性的项目，使用资源有限的维度来改进这种方法。这将对复杂性类的结构产生进一步的定量洞察，对资源受限测度的局限性有新的理解，并更好地评估资源受限测度假设的合理性。更广泛的影响：本研究还将在计算复杂性、信息论、学习理论和分形几何之间建立新的联系，并预期这些领域之间的跨学科互动将产生长期影响。以前不同领域的概念和思想将通过资源边界维度的统一概念得到应用，从而产生新的思维方式。研究结果将作为技术报告和会议出版物广泛提供。将保留所有相关论文的在线参考书目，以帮助研究人员更好地获取文献。来自代表性不足群体的研究生将在该项目中发挥重要作用。

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.