跳到主要内容

空间复杂度类

阐述

TIME

f:NR+f:\mathbb N\to\mathbb R^+,定义空间复杂度类 SPACE(f(n))\operatorname{SPACE}(f(n)) 是所有能在 O(f(n))O(f(n)) 渐近时间内由某种确定性 Turing 机判别的语言的集合。

NTIME

f:NR+f:\mathbb N\to\mathbb R^+,定义空间复杂度类 NSPACE(f(n))\operatorname{NSPACE}(f(n)) 是所有能在 O(f(n))O(f(n)) 渐近时间内由某种非确定性 Turing 机判别的语言的集合。

两者的关系

Savitch 定理指出将非确定性 Turing 机转换为确定性 Turing 机时只需要使用平方大小的空间。

实例

性质

相关内容

参考文献