Abstract:
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.