Search

AF:Small:Collaborative Research:Studies in nonuniformity, completeness, and reachability

Abstract:


Computational complexity theory classifies computational problems into various complexity classes based on the amount of resources needed to solve them. This classification is done by measuring various resources such as time, space, nonuniformity, nondeterminism, and randomness. A better understanding of the relationships among these various resources shed light on the computational difficulty of the problems that are encountered in practice.

Category: 

Study of Nondeterminism

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.

Category: