Collaborative Research: Research in Computational Complexity

计算复杂性理论侧重于理解资源有限计算的能力。该项目的总体目标是对计算复杂性理论的某些主题做出原创性贡献。具体地说，关于明确计算的性质和平均情况的复杂性的基本问题将被调查。在无二义性计算的主题中，将研究无二义性在小空间计算中的作用。在平均情况下，将研究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.