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的平均案例与最差的案例复杂性与位于多项式时间层次结构的各种复杂性类别之间的关系。Broader的影响：该项目解决了计算复杂性理论中的几个基本问​​题。该项目的结果将进一步了解有效计算的性质。由于效率的概念对于所有其他计算领域都是至关重要的，因此这项研究有可能对这些领域进行科学影响。该项目的研究结果将在经过同行评审的期刊上发表，并将在国家和国际会议上介绍，从而使结果广泛传播以增强科学理解。将沿该项目的主题创建和教授新课程，从而整合教学和研究。 该赠款还将用于各种人力资源开发活动，例如支持和指导研究生以及邀请游客。