Research Into Foundations of Computational Complexity

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This proposal is for research into hard open questions concerning the power of various complexity classes. The work will focus on two types of questions. The first deals with showing that certain famous problems are not "too easy". For example, while it is widely believed that SAT requires exponential time, we cannot even prove that there is no linear time Turing Machine for SAT. Our first work will focus on trying to prove modest lower bounds on problems such as SAT. Second we will also investigate harder questions and attempt to find ways to separate complexity classes. These are, of course, very difficult problems but we have a "new" approach that seems promising. In any event we should be able to get some conditional results that will at least add additional evidence to our belief that certain classes are distinct. A word in general about this research. We feel that it is in some sense "high" risk in that the problems are quite hard. However, we feel that unless people work seriously on them they will never be solved. Also we believe that our approaches have enough of a new slant that they may at least partially succeed.