第一章 计算模型
1.1 一些约定
设 \(f\) 是从 01 字符串到 01 输出的映射，称其为 01 函数。这个函数可以用一个集合 \(L(f)=\{x:f(x)=1\}\) 来描述，并把这个集合叫做语言或者决策问题（decision problems）。
记号：\(\langle x,y\rangle\) 表示一个二元组。
举个例子：对于无向图的最大独立集问题，它对应的语言就是 \(\text{INDSET}=\{\langle G=(V,E),k\rangle: \exists S \subset V\ \text{s.t.} |S|\geq k \ \text{and} \ \forall x,y\in S (x,y)\notin E\}\)。
对于一个算法，一般用 \(T(n)\) 表示再输入长度为 \(n\) 的前提下，算法运行完毕所需要的最大基本操作次数。
复杂度记号：\(f=O(g)\) 表示 \(f\) 不超过 \(g\) 的阶，\(f=\Omega(g)\) 反之，\(f=\Theta(g)\) 表示 \(f\) 与 \(g\) 同阶，\(f=o(g)\) 表示 \(f\) 的阶低于 \(g\)，\(f=w(g)\) 反之。
1.2 对计算和效率建立模型
先来一个不太严谨的说法：对于一个 \(f\) 的算法就是一系列规则。每条规则必须是固定的，但是对规则的使用次数没有限制。每条规则涉及以下一种或多种基本操作：
-
从输入（input）读一个 bit。
-
从写字板（scratch pad）或者一个工作空间（working space）读一个 bit。
-
根据读入的结果，在写字板上写一个 bit。
-
根据读入的结果，或是停止并输出答案 0/1，或是选择下一条需要使用的规则并继续。
注意：任何给定的字符集都可以和固定长度的 0/1 字符串构造双射，所以上文中的一个 bit 也可以是某个给定的字符集中的一个字符。
