CAREER: Techniques for Separations and Inclusions of Complexity Classes

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Computational complexity is the study of the inherent difficulty of computational problems. The theory considers various models of computation, such as classical computers, probabilistic computers, and quantum computers. For each of these, it aims to describe how many resources are needed to compute the solution to a problem as a function of the problem size. The most prominent open question in complexity theory is whether the ability to efficiently verify the validity of a candidate solution implies the ability to efficiently compute a valid solution (assuming one exists). The question is usually stated in terms of the corresponding classes of computational problems: Is NP contained in P? Lots of computational problems from virtually any discipline fall in the class NP but are not known to be in P. Therefore, a positive answer to the P versus NP question would have tremendous algorithmic implications. It would also imply a way to break any public-key cryptographic system, as the security of such systems rests on the assumption that a particular problem in NP does not belong to P. This research project aims to develop techniques for determining the relationships between complexity classes like P and NP: separations and inclusions. On the separation side, the investigators focus on techniques that do not suffer from the known pitfalls of relativization and natural proofs. In particular, they concentrate on indirect diagonalization and exhibiting distinguishing properties of complete problems. On the inclusion side, the emphasis lies on efficient classical simulations of time and space bounded probabilistic and quantum computations. The educational goal consists of the development of graduate courses on pseudo-randomness and derandomization and on quantum computing. At the undergraduate level, the investigators plan to further the integration of discrete structures in the core curriculum.