空間層譜定理

空間層譜定理（space hierarchy theorem）是2018年公布的計算機科學技術名詞。

基本介紹

• 中文名：空間層譜定理
• 外文名：space hierarchy theorem
• 所屬學科：計算機科學技術
• 公布時間：2018年

定義

如果 f,g 是空間可構造函式，滿足 f(n) = o(g(n)) ，那么，SPACE( f(n) )SPACE( g(n) )，這裡SPACE( f(n) )是確定型圖靈機在空間 f(n) 內所接受的一切語言構成的類。

出處

《計算機科學技術名詞 》 (第三版)。