On alternation II
On alternation II
复制标题
关于交替 II
DOI：
10.1007/bf00286494
复制
发表时间：
1980
期刊：
影响因子：
0.6
通讯作者：
R. Reischuk
中科院分区：
文献类型：
--
作者：
W. Paul;R. Reischuk
每个确定性的t(N)-时间受限多带图灵机可以用一个交替的t(N)-logt(N)/logt(N)-时间有界图灵机来模拟。如果每个有向无环图的深度可以通过只去掉o(N)条边而减少到对数n，那么在线性时间内，非确定多带图灵机比确定性多带图灵机能够识别更多的语言。对于某些图，要将深度减少到logn，需要删除Ω(n/loglogn)条边。给出了一个图论条件，它表明遗忘降低了多带图灵机的功率。
SummaryEvery deterministic t(n)-time bounded multitape Turing machine can be simulated by an alternating t(n) loglog t(n)/log t(n)-time bounded Turing machine.If the depth of every directed acyclic graph with n edges can be reduced to log n by removing only o(n) edges, then in linear time nondeterministic multitape Turing machines can recognize mor languages than deterministic multitape Turing machines. For some graphs reduction of the depth to log n requires the removal of Ω(n/loglog n) edges. A graph theoretic condition is given, which implies that obliviousness reduces the power of multitape Turing machines.