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.