Collaborative Research: Research in Complexity Theory

合作研究：复杂性理论研究

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

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的平均情况复杂性和最坏情况复杂性与多项式时间层次中的各种复杂性类之间的关系。更广泛的影响：这个项目解决了计算复杂性理论中的几个基本问题。这个项目的结果将进一步加深我们对高效计算本质的理解。由于效率的概念是所有其他计算领域的核心，因此这项研究有可能对这些领域产生科学影响。该项目的研究成果将在同行评审的期刊上发表，并将在国家和国际会议上介绍，从而能够广泛传播成果，以提高科学认识。新课程将沿着这个项目的主题创建和教授，从而将教学和研究结合起来。这笔赠款还将用于各种人力资源开发活动，如支持和指导研究生和邀请来访者。