Study of Nondeterminism

非决定论研究

• 批准号: 0430807
• 负责人: Pavan Aduri
• 金额: $ 17.94万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430807&HistoricalAwards=false
• 关键词: Study; Nondeterminism

Understanding the power of nondeterminism is one of the most fundamental problems in theoretical Computer Science. Many problems that arise in practice fall into the nondeterministic class NP. A lot of effort has been put, by many researchers, in understanding various aspects and properties the class NP. The goal of this project is to enhance our current understanding of the class NP.Intellectual Merit: This project studies the structure of NP in the average-case world and seeks to develop new techniques to understand relations among NP and related classes in the average-case realm. This would bring out new connections between average-case and worst-case complexities of NP. The nonuniform complexity of NP and related classes will be investigated. This work attempts to understand the intrinsic properties of NP-complete sets. All these investigations will help us gain more insight into the nature of nondeterminism.Broader Impact: A goal of the project is to unearth connections among several hypotheses that have been previously used in different contexts. This effort could help in unifying some of the underlying concepts of these hypotheses. This might pave way to make progress on some basic problems. The results of the research will be integrated into advanced courses. The course materials, in the form of lecture notes, will be made available on the web. The informal seminars will form collaborative efforts among students and faculty from two different universities. All results of the research will be broadly distributed to the scientific community, and will be posted on line at ECCC. Results will be submitted to major scientific conferences.

了解非确定性的力量是理论计算机科学中最根本的问题之一。实践中出现的许多问题属于非确定性的NP。许多研究人员为理解NP类的各个方面和财产所付出了很多努力。该项目的目的是增强我们对NP类的当前理解。智能优点：该项目研究了平均案例世界中NP的结构，并试图开发新的技术来了解平均案例领域中NP和相关类之间的关系。 这将带来NP平均案例和最差的复杂性之间的新联系。 NP和相关类别的非均匀复杂性将被研究。这项工作试图了解NP完整集的内在属性。所有这些调查将有助于我们对非确定性的性质有更多的了解。BRODERIMPACT：该项目的目标是在以前在不同情况下使用的几种假设中发掘联系。 这种努力可以帮助统一这些假设的一些基本概念。这可能铺平了在一些基本问题上取得进展的方法。研究结果将融入高级课程中。该课程材料以讲义的形式将在网络上提供。非正式研讨会将在两所不同大学的学生和教职员工之间进行合作努力。该研究的所有结果将大致分发给科学界，并将在ECCC上发布。结果将提交主要的科学会议。