Space Complexity
度量复杂性
- 是一个在所有输入上都停机的确定型图灵机， 的空间复杂度是一个函数
- 是 在任何长为 的输入上扫描带子方格的最大数
- 若 的空间复杂度为 ，则称 在空间 内运行
- 空间复杂性类定义如下
- 萨维奇定理
- 任何消耗 空间的非确定型图灵机都可以转为仅消耗 空间的确定型图灵机
Savitch’s theorem
PSPACE 类
PSPACE 完全性
PSPACE-complete
若语言 满足下面两个条件，则它是PSPACE完全的：
- PSPACE 中的每一个语言 多项式时间可归约到
- 若 只满足第二个条件，则称它为 PSPACE 难的 (PSPACE-hard)
TQBF 问题
True Quantified Boolean Formula
量词化布尔公式
布尔公式是包含布尔变量、 常数0和1以及布尔运算符 的表达式。
现在定义更一般形式的布尔公式。
- ：全称量词 (Universal quantifier)
- ：存在量词 (Existential quantifier)
- 紧跟在量词后面的变量 x 受到该量词约束 (bound)
- 量词的作用范围是跟在变量后括弧内出现的语句段，该段称为量词的辖域 (scope)
- 例如 ，显然这个命题为真。
- 当解释包含量词的语句的含义时，必须考虑所取值的域 (universe)。
- 在这个例子中，域是自然数，但是如果改用实数，则该命题为假。
带量词的布尔公式称为量词化布尔公式 (Quantified Boolean formula)，域是{0,1}。
证明 是 PSPACE 完全的
- 构造一个多项式空间算法 （显然判定 ）
- 为了分析它的空间复杂性， 我们发现它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值，所以空间总消耗是 ， 其中 m 是 中出现的变量个数。因此 T 在线性空间内运行。
- 设 A 是一个由图灵机 空间内判定的语言，k 是某个常数。
下面给出一个从 A 到 TQBF 的多项式时间归约。
…
L 类和 NL 类
之前只考虑了时间和空间复杂性界限至少是线性的情况， 即界限 至少是 n。
现在考察更小的亚线性 (sublinear) 空间界限，即 。
- 在时间复杂性中，亚线性界限还不够读完输入，所以不考虑它们。
- 萨维奇定理对于亚线性空间界限也成立。
：L 是确定型图灵机在对数 (exponential) 空间内可判定的语言类
：NL 是非确定确定型图灵机在对数空间内可判定的语言类
对于至少是线性的空间界限，双带图灵机模型等价于标准的单带模型。
对于亚线性空间界限， 只采用双带模拟。
- 引入一种有两条带子的图灵机：一条只读输入带和一条读写工作带。
- 在只读带上输入头能读取符号，但不能改变它们。这个头必须停留在包含输入的那部分带子上。可以给机器提供一个方法，使它能够检测读写头处于输入的左端和右端的时刻。
算法分析
在之前的内容中描述了一个判定的图灵机， 它左右来回扫描输入，删掉匹配的0和1。该算法用线性空间记录哪些位置已经被删掉了，但可以将它修改为使用对数空间。判定的对数空间图灵机不能删除输入带上已经匹配的0和1，因为该带是只读的。使机器在工作带上用二进制分别数 0 和 1 的数目，唯一需要的空间是用来记录这两个数。
在二进制形式下，每个计数器只消耗对数空间， 因此算法在 空间内运行。
- 即
之前证明 PATH 属于 P, 但是给出的算法消耗线性空间。目前还不清楚 PATH 是否能确定性地在对数空间内解决，但是的确知道一个判定 PATH 的非确定性的对数空间算法。
判定 PATH 的非确定型对数空间图灵机从结点 s 开始运算，非确定地猜测从 s 到 t 的路径的每一步。机器在工作带上只记录每一步当前结点的位置，而不是整条路径（否则将超出对数空间的要求）。
机器从当前结点所指向的结点中非确定地选择下一个结点。它反复执行这一操作， 直至到达结点t而接受，或者执行 m 步以后拒绝，其中 m 是图中的结点。
- 即
NL 完全性
若语言 满足下面两个条件，则它是 NL完全的：
- NL 中的每一个语言 对数时间可归约到
推论：若有一个 NL 完全语言属于 L， 则 。
定理：