算法（H）笔记——决定问题
本文最后更新于 2026年7月8日 20:26:21
decision problem 判定问题：回答是或否
一、定义
算法：长度固定，与输入无关的code，用于解决问题
如果可以在有限时间内解决，这个问题是可判定的
可判定性：
- 程序个数是|N|，可数无限
- 问题个数是|R|，不可数无限
结论：大部分decision problem无法用程序解决
- 复杂度
- R：在有限时间内可以解决的问题
- EXP：在指数时间内可以解决
- P：在多项式时间内可以解决
\(P<EXP<R\)
- NP：在多项式时间内可以被证明
- 最终答案是yes，给出一定信息，某人可以在多项式时间内证明
- no，则不存在这样的证据
\(P<=NP,NP<=EXP\)
二、规约 reduction
在多项式时间内，将问题A转换成B，并将B的解作为A的解。而B是我们已知如何求解的
- NP-hard：如果任何NP问题都能被多项式规约至问题A，则A是NP-hard的
- NP-complete=NP∩NP-hard；所有NP-完全问题都是彼此相等的，也就是对彼此都互相可多项式规约
第一个NP-完全：SAT问题：使得一个电路可连通
最长简单路径和俄罗斯方块是NP-完全问题
棋类问题是EXP-完全问题
NP-完全问题：
三色问题
clique cover问题：一个图能不能分成k个团（团中两个点都相互连接）
三色问题可以多项式规约至cc问题：做补图（连接的改成不连接，不连接的连上），看是否有k=3的cc
哈密顿：经过所有顶点一次且仅一次
- 哈密顿回路问题
- 哈密顿path问题
哈密顿回路可被规约成哈密顿path问题：
遍历所有边，将一条边隔断，两个顶点分别向外连出一条线段，线段的另一端作为起点和终点，然后跑哈密顿path算法
三、总结各类NPC问题
独立集：取补图可转换成clique问题（能不能找到>=k个点，彼此两两连接），所以is<=clique
反过来clique取补图可以转换成独立集问题，所以clique<=is
S 是 G 中的团⟺S 是 Gˉ 中的独立集
VC：顶点覆盖问题。找<=k的子集C\(\iff\)找>=N-k的IS
反过来，找>=k的IS是否存在\(\iff\)找<=N-k的子集C
子集 \(C\) 是一个顶点覆盖（VC），当且仅当它的补集 \(V \setminus C\) 是一个独立集（IS）
clique cover问题：一个图能不能分成<=k个团（团中两个点都相互连接）
三色问题可以多项式规约至cc问题：做补图（连接的改成不连接，不连接的连上），看是否有k<=3的cc；反过来cc到3-color也是做补图，看三色问题有没有解；3可以替换成k
三色问题本质是找有没有k个IS
哈密顿回路可被规约成哈密顿path问题：
遍历所有边，将一条边隔断，两个顶点分别向外连出一条线段，线段的另一端作为起点和终点，然后跑哈密顿path算法
哈密顿路径到哈密顿回路：添加一个连接所有顶点的万能节点
- 如果限制起终点，新增节点只连接这两个点
最后得到回路，从起始点开始读取，然后剪断即可
哈密顿图：包含哈密顿回路的图