Research Into Foundations of Computational Complexity

这个提议是为了研究关于各种复杂性类别的力量的开放性难题。 这项工作将侧重于两类问题。 第一个是关于证明某些著名的问题并不“太容易”。 例如，虽然人们普遍认为SAT需要指数时间，但我们甚至无法证明SAT不存在线性时间图灵机。 我们的第一个工作将集中在试图证明适度的下限问题，如SAT。 其次，我们也将研究更难的问题，并试图找到分离复杂性类的方法。 当然，这些都是非常困难的问题，但我们有一个“新”的办法，似乎很有希望。 无论如何，我们应该能够得到一些条件性的结果，这些结果至少会为我们相信某些类是不同的增加额外的证据。关于这项研究的一句话。 我们认为，从某种意义上说，这是“高”风险，因为问题相当棘手。 然而，我们认为，除非人们认真对待这些问题，否则这些问题永远不会得到解决。 此外，我们相信我们的方法有足够的新倾向，它们至少可以部分成功。

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.