Study of Nondeterminism

理解非确定性的力量是理论计算机科学中最基本的问题之一。在实践中出现的许多问题都属于非确定性NP类。许多研究者在理解NP类的各个方面和性质方面做了大量的工作。这个项目的目标是提高我们目前对NP类的理解。智力优势：这个项目研究NP在平均情况下的结构，并寻求开发新的技术来理解NP和平均情况领域的相关类之间的关系。 这将带来NP的平均情况复杂性和最坏情况复杂性之间的新联系。 NP和相关类的非一致复杂性将被研究。本文试图理解NP完备集的内在性质。所有这些调查将帮助我们更深入地了解非决定论的本质。更广泛的影响：该项目的一个目标是挖掘以前在不同背景下使用的几个假设之间的联系。 这一努力可能有助于统一这些假设的一些基本概念。这可能为在一些基本问题上取得进展铺平道路。研究结果将纳入高级课程。课程材料将以课堂讲稿的形式在网上提供。非正式研讨会将形成来自两所不同大学的学生和教师之间的合作努力。所有研究结果将广泛分发给科学界，并将在ECCC在线发布。研究结果将提交给主要的科学会议。

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.