Collaborative Research: Research in Computational Complexity

合作研究：计算复杂性研究

• 批准号: 0830730
• 负责人: Vinodchandran Variyam
• 金额: $ 10.41万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830730&HistoricalAwards=false
• 关键词: Collaborative; Research; Computational; Complexity

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.

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