数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究在 TOC 中，证明线性有界自动机 LBA ⊂ PSPACE？
线性有界自动机 (LBA) 是一种受限形式的图灵机，其输入磁带是有限的。
示例
证明 LBA ⊂ PSPACE
PSPACE 是上下文相关语言集合的超集。
现在证明 LBA=PSPACE，
我们使用磁带缩减的空间压缩定理，该定理指出，
对于每个 k 磁带 S(n) 空间有界离线图灵机 M 和常数 c>0，存在一个磁带 cS(n) 空间有界离线图灵机 N，使得 L(M)=L(N)。
以下恒等式成立 −
DSPACE(S(n))=DSPACE(O(S(n)))
和 NSPACE(S(n))=NSPACE(O(S(n)))
由于 LBA 是一个磁带 n 空间有界图灵机，因此如下所述 −
LBA=NSPACE(n)---------------------(1)
现在根据萨维奇定理，如果 S 是完全空间可构造且 S(n)>log(n)，则
NSPACE(S(n)) ⊆DSPACE(S^{2}(n)) -------------(2)
最终证明
LBA=NSPACE(n)............by(1)
⊆DSPACE(n^{2})............by(2)
⊂DSPACE(n^{3})............by 空间分层定理
⊆PSPACE
然后，空间层次结构需要完全空间可构造的 S(n)。
更新于： 2021 年 6 月 16 日
296 个浏览量
广告