資料結構
網路
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 個瀏覽量
廣告