论文标题
p不完整的集合以减少logspace-
Incomplete sets in P for logspace-reduction
论文作者
论文摘要
在本文中，我们研究了TMS的行为，并具有时间限制和磁带空间限制。当时间限制一致编码时，此问题在P中。如果两个限制都归功于无穷大，则不可确定哪些限制将超过限制。因此，可以构建p中的logspace-分配集。这意味着l $ \ not = $。
In this article, we investigate the behaviour of TMs with time limit and tape space limit. This problem is in P when the time limit is unary coded. If both limits go to infinity, it is undecidable which limit is exceeded first. Thus logspace-incomplete sets in P can be constructed. This implies L $\not=$ P.
