This article shows that PSPACE not equal EXP. A simple but novel proof technique has been used to separate these two classes. Whether an arbitrary Turing machine accepts an input when the running time is limited has been computed in this paper. Then, the limit goes to infinity. Thus, methods of the recursion theory can be applied to problems of computational complexity theory without violating the relativization barrier.
翻译:此文章显示 PSPACE 并不等于 EXP 。 使用简单而新颖的证明技术来区分这两个类别。 本文中计算了运行时间有限时, 任意的图灵机器是否接受输入。 然后, 限制是无限的。 因此, 递归理论的方法可以适用于计算复杂度理论的问题, 而不违反相对化屏障 。