Collaborative Research: Research in Complexity Theory

计算复杂性理论侧重于理解资源受限计算的能力。这个项目的广泛目标是对计算复杂性理论中的某些主题做出原创性的贡献。具体地说，关于明确计算的性质和平均情况复杂性的基本问题将被调查。在无歧义计算的主题中，将研究无歧义在小空间计算中的作用。在平均情况复杂性方面，将研究NP的平均情况复杂性和最坏情况复杂性之间的关系，以及位于多项式时间层次中的各种复杂性类别。更广泛的影响：这个项目解决了计算复杂性理论中的几个基本问题。这个项目的结果将进一步加深我们对高效计算本质的理解。由于效率的概念是所有其他计算领域的核心，这项研究有可能对这些领域产生科学影响。该项目的研究成果将发表在同行评议的期刊上，并将在国家和国际会议上发表，从而使研究成果得以广泛传播，以增进对科学的理解。将根据该项目的主题创建和教授新课程，从而将教学和研究结合在一起。这笔赠款还将用于各种人力资源开发活动，如支持和指导研究生以及邀请来访者。

Computational complexity theory focuses on understanding capabilities of resource bounded computations. The broad goal of this project is to make original contributions to certain topics in computational complexity theory. Specifically, fundamental questions regarding the nature of unambiguous computations and average-case complexity will be investigated. In the topic of unambiguous computations, the role of unambiguity in small space computations will be investigated. In average-case complexity, the relations between average-case and the worst-case complexity of NP and various complexity classes that lie in the Polynomial-time Hierarchy, will be investigated. Broader Impacts: This project addresses several basic questions in computational complexity theory. The results from this project will further our understanding of the nature of efficient computation. Since the notion of efficiency is central to all other areas of computing, this research has potential to scientifically impact these areas. Research results from this project will be published in peer-reviewed journals and will be presented at national and international conferences, thus enabling broad dissemination of the the results to enhance scientific understanding. New courses will be created and taught along the themes of this project, thus integrating teaching and research. The grant will also be used for various human resource development activities such as supporting and mentoring graduate students and inviting visitors.