计算问题、表示与正确性

“找一条最快路线”还不是一个足以分析的计算问题。最快可能指距离最短、预计时间最少、费用最低或换乘次数最少；道路可能单向、临时关闭或随时间改变；终点不可达时，程序可能需要返回特殊结果。任何一项差异都可能改变正确答案、可用算法和资源成本。

算法研究首先需要固定：输入是什么，输出是什么，什么算正确，哪些输入属于适用范围。

1. 问题、实例、解、算法与执行

这些对象处于不同层次。

以最大公约数为例：

问题：给定两个不同时为零的非负整数，输出它们的最大公约数；
实例：输入 $(48,18)$ ；
解：输出 $6$ ；
算法：反复执行 $(a,b)\leftarrow(b,a\bmod b)$ 直到 $b=0$ ，再输出 $a$ ；
实现：用某种编程语言和整数表示写成程序；
一次执行：某个实现处理 $(48,18)$ 时经历 $(48,18)\to(18,12)\to(12,6)\to(6,0).$

问题描述一整族输入；实例是其中一份具体输入；解只对应当前实例；算法是一套统一规则；实现把算法放入具体计算环境；一次执行是实现处理某个实例时发生的过程。

只会处理一个固定输入，不构成解决一般问题的算法。若程序永远只接收 $(48,18)$ ，它可以直接输出 6，但这没有说明怎样处理更大或不同的输入。

2. 集合、元素与关系

为了精确表达问题，需要少量集合语言。

集合是一组对象。例如：

I=\{\text{全部合法输入}\}

表示合法输入集合。若对象 $x$ 属于集合 $I$ ，写作：

x\in I.

若不属于，写作：

x\notin I.

设 $I$ 是输入集合， $O$ 是可能输出的集合。一个输入和一个输出组成有序对 $(x,y)$ 。全部这类有序对构成的集合记作：

I\times O,

称为笛卡尔积。

计算问题可以用一个正确性关系表示：

R\subseteq I\times O.

当 $(x,y)\in R$ 时，表示 $y$ 是输入 $x$ 的合法答案。为了简洁，也写成：

R(x,y).

因此，一个计算问题可以写成：

\Pi=(I,O,R).

符号 $\Pi$ 只是这个问题的名称。

对于固定输入 $x$ ，它的全部合法答案组成集合：

\operatorname{Ans}_\Pi(x)=\{y\in O:R(x,y)\}.

同一个输入可以有多个正确输出。图中可能有多条同样短的路径，布尔公式可能有多组满足赋值，一个依赖系统也可能有多种合法执行顺序。使用关系，而不是强迫每个输入对应唯一输出，可以直接表达这种情况。

若每个输入恰好对应一个输出，就得到函数。函数通常写作：

f:I\to O.

它表示每个 $x\in I$ 都有唯一的 $f(x)\in O$ 。函数是关系的一种特殊情形。

3. 算法解决问题的含义

设确定性算法 $A$ 接收输入 $x$ ，输出记为 $A(x)$ 。它解决问题 $\Pi=(I,O,R)$ ，需要满足：

\forall x\in I, \quad A\text{ 在输入 }x\text{ 上停止，并且 }R(x,A(x)).

符号 $\forall$ 读作“对于所有”。这句话包含两个独立条件：

对每个合法输入，算法最终停止；
停止时输出是合法答案。

“如果算法停止，它就不会给错答案”只叫部分正确性；它仍可能在某些输入上永远运行。总正确性要求部分正确性和终止性同时成立。

例如，一个程序不断扫描数组，看到目标就返回下标，但目标不存在时永远从头重扫。它若返回，返回值可能总是正确；但它不能完成“目标不存在时返回 $\bot$ ”的任务。符号 $\bot$ 常用来表示“无解”或“没有找到合法对象”的特殊输出。

立即返回 $\bot$ 的程序总会停止，却会错过真正有解的输入。终止不能代替正确，正确输出也不能代替终止。

4. 前置条件与后置条件

算法结论总有适用范围。

二分查找要求数组已经按非递减顺序排列：

A[i]\leq A[i+1].

这叫前置条件。若算法返回下标 $i$ ，则应满足：

0\leq i<n \quad\text{并且}\quad A[i]=t.

若返回 $\bot$ ，则数组中不存在等于目标值 $t$ 的元素。这些是后置条件。

输入不满足前置条件时，算法可以失效，但不能据此否定原定理；如果原任务允许任意数组，那么该算法只是不足以解决更广的问题。

前置条件必须属于问题或算法说明，不能藏在例子里。非负边权、图已连通、输入保证有解、整数不会溢出，都可能决定结论是否成立。

5. 逻辑中的“如果”“当且仅当”与量词

算法和复杂性定义经常需要区分单向条件与双向等价。

若命题 $P$ 成立能够推出命题 $Q$ 成立，写作：

P\Rightarrow Q.

这表示 $P$ 是 $Q$ 的充分条件， $Q$ 是 $P$ 的必要条件。

若两个方向都成立：

P\Rightarrow Q \quad\text{并且}\quad Q\Rightarrow P,

写作：

P\iff Q,

读作“ $P$ 当且仅当 $Q$ ”。

符号 $\exists$ 读作“存在”。例如：

\exists y,\ R(x,y)

表示至少存在一个输出 $y$ ，使它是输入 $x$ 的合法答案。

否定一个存在陈述，会变成全称陈述：

\neg\exists y\,P(y) \iff \forall y\,\neg P(y).

也就是说，“不存在一个满足条件的对象”等价于“所有对象都不满足条件”。这一区分后来会成为 YES 证书与 NO 证书差异的基础。

6. 不同任务类型

同一数学对象可以产生不同计算任务。

设 $\varphi$ 是一个布尔公式。布尔变量只取真或假；赋值为每个变量指定一个真值。

求值

输入公式和一组完整赋值，输出公式的真值。

判定

问是否存在某组赋值使公式为真：

\exists a,\ \varphi(a)=\mathrm{true}\ ?

输出只有 YES 或 NO。

搜索

若公式可满足，输出一组满足赋值；若不可满足，输出 $\bot$ 。

优化

若公式由许多子句组成，找一组赋值，使满足的子句数最多。

设 $F(x)$ 是实例 $x$ 的可行解集合， $m(x,y)$ 是解 $y$ 的目标值，则最大化问题的最优值为：

\operatorname{OPT}(x)=\max_{y\in F(x)}m(x,y).

输出最优值和输出达到最优值的具体解，是相关但不同的任务。

计数

输出满足赋值的总数：

\#\operatorname{SAT}(\varphi) = |\{a:\varphi(a)=\mathrm{true}\}|.

竖线在集合外表示元素数量。

枚举

输出全部满足赋值。若公式有 $n$ 个变量且没有实质约束，可能有 $2^n$ 组结果；完整输出本身已经很大。

这些任务共享输入对象，却要求交付不同信息。复杂度分类必须针对明确任务，而不是只针对“SAT”“旅行商”或“背包”这类宽泛名称。

7. 合法输入、无解实例与承诺范围

以下三种情况不同。

输入格式本身非法；
输入合法，但没有满足条件的解；
输入没有满足算法声明的前置条件。

字符串 x ∧ ∨ y 可能不是合法公式；公式

x\land\neg x

语法合法，只是不可满足；未排序数组对二分查找而言处于承诺范围之外。

若算法只需处理某一类输入，可以把这些条件明确写入输入集合 $I$ 。也可以使用承诺问题：把输入分成需要回答 YES 的集合和需要回答 NO 的集合，对承诺之外的输入不作要求。

无解时的输出也必须明确。搜索失败不等于证明无解。随机尝试一千个候选没有成功，只能排除这批候选；若候选空间远大于此，不能据此返回 $\bot$ 。

8. 编码与输入长度

算法实际接收的是有限字符串，而不是抽象对象本身。用：

\langle X\rangle

表示对象 $X$ 的编码。

二进制字母表为：

\Sigma=\{0,1\}.

由这些符号组成的有限字符串长度记作 $|x|$ 。若输入编码为 $x=\langle X\rangle$ ，输入规模通常定义为：

n=|x|.

整数的数值大小和编码长度不是同一件事。若正整数 $N$ 的二进制表示有 $n$ 位，则：

2^{n-1}\leq N<2^n.

所以数值 $N$ 可以接近 $2^n$ 。一个从 1 循环到 $N$ 的过程，虽然按数值写成 $O(N)$ ，按输入位数看却接近 $O(2^n)$ 。

编码必须能够明确解析，也不能通过任意冗余把同一对象写得无限长。二进制、十进制、邻接矩阵和边列表可能具有不同长度，但合理编码通常能够在多项式开销内互相转换。把长度为 $n$ 的输入后面补上 $2^n$ 个无意义符号，会人为改变规模，不能当作原问题的免费加速。

9. 输出长度也是成本

算法至少需要足够时间写出自己的输出。

若一个任务要求显式输出 $2^n$ 个不同对象，每个对象占 $n$ 位，那么输出长度至少为：

\Omega(n2^n).

任何完整枚举算法都无法在小于这个数量级的时间内打印全部结果。

计数任务可能只输出数字 $2^n$ ，它的二进制表示只有 $n+1$ 位。短输出不表示计算一定容易，但说明计数与枚举拥有不同的最低成本。

输出全部对象、输出对象数量、输出一个压缩表示，是三种不同契约。

10. 正确性证明的基本结构

测试可以发现错误，却通常不能证明对无限多或巨大数量的输入都正确。算法证明需要覆盖所有合法输入和所有返回路径。

循环不变量

循环不变量是在每次迭代开始时都成立的陈述。证明通常包括：

初始化：第一次迭代前成立；
保持：一次迭代后仍成立；
退出：不变量与退出条件共同推出后置条件。

二分查找可以维护：

如果目标存在，那么至少一个目标位置仍在当前候选区间内。

每次比较中间元素后，只删除不可能含有目标的一半。

终止还需要一个严格进展量。例如候选区间长度是非负整数，并在每次未返回的迭代中严格减小，因此不可能无限执行。

递归与归纳

递归算法调用自己处理更小实例。证明需要：

基础情形正确；
递归调用处理严格更小实例；
假设较小实例正确后，组合步骤能得到当前实例的正确答案。

交换论证

贪心算法常需证明：某个局部选择可以安全固定。取任意最优解，若它没有采用该选择，就把其中一部分替换成贪心选择，并证明可行性和目标值不变差。

反例与边界

一个反例足以否定“对所有输入都成立”的主张。空输入、重复元素、无解实例、相等权重和极端数值经常暴露遗漏的前置条件或返回路径。

11. 算法结论的完整构成

一项可靠算法结论至少需要说明：

解决什么任务；
输入如何表示；
哪些前置条件成立；
算法如何运行；
为什么停止；
为什么输出正确；
使用什么计算模型；
时间、空间或其他资源成本；
哪些内容没有被该结论保证。

问题定义、表示和正确性不是分析前的手续。它们决定我们究竟在证明什么，也决定后续复杂度数字是否有意义。