6.6 Intractability：P、NP、完全性与工程取舍

6.6 · Intractability覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“6.6 · Intractability”如何区分 P、NP、NP-hard 与 NP-complete，并用多项式归约和证书验证指导工程取舍
能逐项核对难解性、计算复杂性、多项式时间、P与NP、NP完全性、应对难解问题，并区分作者站内容与本页独立补充
能按“若 A ≤p B 且 B 有多项式算法，则 A 也有多项式算法；困难性证明使用相反推论方向”手算一个最小输入，逐步检查“NP 结论必须给出多项式长度证书和多项式验证器；NP-hard 必须保持归约方向”
能注入“从目标难题归约到已知难题却声称目标 NP-hard，或把尚未证明的 P≠NP 当作定理”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“6·6 · Intractability”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“6·6 · Intractability”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“6·6 · Intractability”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：6.6 · Intractability

1. 难解性：在本页通过“定义判定问题”连接解释、交互状态和练习验收。
2. 计算复杂性：在本页通过“写出证书验证器”连接解释、交互状态和练习验收。
3. 多项式时间：在本页通过“选择已知困难源问题”连接解释、交互状态和练习验收。
4. P与NP：在本页通过“构造多项式归约”连接解释、交互状态和练习验收。
5. NP完全性：在本页通过“核对方向与工程策略”连接解释、交互状态和练习验收。
6. 应对难解问题：在本页通过“定义判定问题”连接解释、交互状态和练习验收。

从“硬件快一万亿倍，为什么仍救不了穷举”开始

难解性（intractability）不是“当前程序写得慢”，而是关于所有可能算法的resource question。

先预测：一台机器快 $10^{12}$ 倍，能把 $2^N$ brute force可处理的N提高多少？因为：

2^{N+40}\approx 10^{12}\cdot2^N

只增加约40个binary choices。对 $N!$ 的改善更有限。Exponential growth最终会吞掉硬件、并行度和常数优化。

但“exponential algorithm”不等于every input都慢，也不等于problem已被证明没有polynomial algorithm。Complexity theory研究worst-case resource class；工程上仍可能有大量easy instances。

6.6.1 Computational complexity：从一个算法转向所有算法

计算复杂性（computational complexity）与algorithm analysis层次不同：

Algorithm analysis证明某个implementation的upper bound或lower bound。
Computational complexity试图证明任何conceivable algorithm都不能越过某resource boundary。
Complexity class把拥有共同resource bound的problems归组。

Turing machine提供machine-independent formal model；polynomial changes of reasonable machine models通常不改变P这类粗粒度class。结论仍必须说明input encoding、deterministic或randomized、decision或search，以及worst-case或average-case。

若当前best TSP algorithm是 $O(2^N N^2)$ ，这只是upper bound；trivial input-read给 $\Omega(N)$ lower bound。二者之间的巨大gap正是complexity研究的问题，不能因“尚未找到更快算法”就宣布lower bound。

6.6.2 Input size是表示长度，不是数值大小

整数N的binary encoding length：

b=\lfloor\log_2N\rfloor+1

Trial division到 $\sqrt N$ 需要约 $2^{b/2}$ candidates，因此是input bits b的exponential time，不是polynomial time。Complexity必须以读入的symbols数量计量。

类似地，knapsack dynamic programming的O(nW)若W用binary表示，可能对input length是pseudo-polynomial；若weights以unary encoding，W本身就是input length的一部分，分类会不同。

6.6.3 Polynomial time为何成为tractability边界

多项式时间（polynomial time）指存在constants c、k：

T(n)\le c n^k

Polynomial algorithms具备三项重要closure properties：compose仍是polynomial；reasonable encodings之间的polynomial conversion不改变分类；规模扩大时增长通常比exponential稳健。

这不是“所有polynomial都实用”。 $n^{100}$ 或 $10^{100}n^2$ 仍不可运行；而well-engineered exponential solver可能快速解决现实分布中的许多instances。Polynomiality是理论上的scalability surrogate，不是latency SLA。

Official 6.6把没有polynomial-time algorithm的问题称为intractable。对NP-complete problems，尚未证明它们不在P；准确表述是：若P不等于NP，则所有NP-complete problems都没有polynomial-time deterministic algorithm。

6.6.4 Decision、search与optimization

Decision problem输出YES/NO；search problem要找witness；optimization problem要找best feasible solution。以TSP为例：

Decision：是否存在cost至多L的tour？
Search：找一条cost至多L的tour。
Optimization：找minimum-cost tour。

Decision YES witness是一条tour，可快速验收。若edge weights是bounded integers，可对L做binary search找到optimal value，并通过self-reduction逐步固定edges恢复tour，因此三种forms常在polynomial factors内equivalent。

function tspDecision(graph: Graph, limit: number, tour: Vertex[]) {
  if (tour.length !== graph.vertexCount + 1) return false;
  if (tour[0] !== tour[tour.length - 1]) return false;
  if (!visitsEveryVertexExactlyOnce(tour.slice(0, -1))) return false;
  return cost(graph, tour) <= limit;
}

Optimization certificate只给candidate objective，通常不能直接证明“没有更优答案”。Decision threshold把optimality转成existence query，便于放入NP框架。

6.6.5 P：能高效求解

P是deterministic machine能在polynomial time解决的decision problems。BFS reachability、sorting decision variants、GCD、shortest paths与linear equations都属于P。

若solver在polynomial time返回answer，那么verifier当然也可运行solver或直接检查answer，所以：

\mathrm{P}\subseteq\mathrm{NP}

“P problem”不保证所有known implementations都快；它说明至少存在一个polynomial algorithm。Reduction也会扩大polynomial degree和constants，所以class membership比production performance更粗。

6.6.6 NP：YES certificate可高效验证

NP是YES instances拥有polynomial-size certificate，且deterministic verifier在polynomial time接受的decision problems。形式上，language L属于NP，当且仅当存在polynomial p与verifier V：

x\in L \iff \exists w,\ |w|\le p(|x|) \text{ and }V(x,w)=1

重点是certificate长度也必须polynomial。若w本身长达 $2^n$ ，即便逐bit检查linear，也不能证明membership in NP。

SAT的witness是one Boolean value per variable。Verifier扫描clauses，只要每个clause至少有one true literal就accept，时间O(formula length)。

function verifyCNF(clauses: Literal[][], assignment: boolean[]) {
  for (const clause of clauses) {
    if (!clause.some((lit) => evaluatesTrue(lit, assignment))) return false;
  }
  return true;
}

TSP decision的witness是vertex permutation，检查uniqueness、edge existence、return-to-start与cost bound都可polynomial完成。

NP里的N来自nondeterministic polynomial time，不是“non-polynomial”。Nondeterministic machine可猜certificate再verify；certificate definition与该machine definition等价。

6.6.7 P and NP：会验证是否等于会寻找

P与NP（P and NP）的open question是：

\mathrm{P}\stackrel{?}{=}\mathrm{NP}

若相等，所有polynomially verifiable YES witnesses都能polynomially找到；若不等，至少有NP problems可快验却不能deterministically快解。

截至本章依据的官方框架，P versus NP仍未解决。不能把“几十年没人找到algorithm”当proof，也不能把某个solver在benchmark上很快当polynomial worst-case guarantee。

co-NP关注NO instances是否有polynomial certificates。例如compositeness的YES witness是factor；primality则最终也被证明在P。NP与co-NP是否相等同样未知，不能凭YES verifier推断NO verifier。

6.6.8 NP-hard与NP-complete

NP完全性（NP-completeness）需要两部分：

Membership：X in NP，给出polynomial certificate与verifier。
Hardness：every problem in NP polynomially reduces to X。

NP-hard只要求“若它能polynomial解决，则P=NP”，problem可能是search、optimization，甚至不属于NP。NP-complete限定为NP内的decision problems。

Cook-Levin theorem证明SAT是NP-complete：任意polynomial-time nondeterministic computation都可编码为polynomial-size Boolean formula，local clauses约束每个time-step/state/tape-cell transition，formula satisfiable恰好对应accepting computation。

Universality的力量在于只需一个seed NP-complete problem。之后若SAT reduce to 3-SAT、3-SAT reduce to independent set、independent set reduce to vertex cover，就通过transitivity不断扩展catalog。

6.6.9 如何正确证明新问题NP-complete

若X已知NP-complete，要证明新问题Y：

X\le_p Y

然后独立证明Y in NP。方向是把known-hard instance编码进candidate Y。

function proveCandidateY(instanceX: X): Y {
  const y = polynomialMap(instanceX);
  assert(isYesX(instanceX) === isYesY(y));
  assert(encodedSize(y) <= polynomial(encodedSize(instanceX)));
  return y;
}

若反过来证明 $Y\le_p X$ ，只能说明Y不比X难，可能给Y一个upper bound；不能传入X的hardness。

6.6.10 3-SAT到Independent Set的证书保留

给3-CNF formula的每个clause创建three literal vertices；同clause内全连接，互补literals之间也连edge。问是否有size等于clause count k的independent set。

若formula satisfiable，每个clause选一个true literal；同clause只选一个，且不会同时选x与not-x，因此构成size-k independent set。
若有size-k independent set，clause clique迫使每clause恰选一个，complement edges保证selected literals consistent，可扩展为satisfying assignment。

Vertices与edges增长polynomial；construction和answer lift也polynomial。这同时证明YES equivalence与witness correspondence。

Reduction verifier应检查clause gadgets、conflict edges、size target以及both directions of proof，而非只用几个examples测试。

6.6.11 TSP为何是典型难解问题

TSP decision in NP，因为tour可快验；通过Hamiltonian cycle等known NP-complete problem可证明TSP decision NP-hard，所以它NP-complete。Optimization TSP通常称NP-hard。

Brute force枚举tour约N!；Held-Karp dynamic programming约 $O(N^2 2^N)$ ，是巨大改进但仍非polynomial。NP-completeness不表示“没有algorithm”，只表示若P不等于NP，就没有能保证polynomial time解决all arbitrary instances的exact algorithm。

Complexity是worst-case statement。Branch-and-bound、cutting planes和modern SAT/ILP solvers可处理许多large structured instances，却仍可能遇到exponential cases。

6.6.12 Coping with intractability：放松三项保证之一

应对难解问题（coping with intractability）时，若P不等于NP，不能同时对NP-complete optimization保证：

Polynomial worst-case time。
Optimal solution。
Arbitrary instances。

放松time guarantee：仍求exact

对规模较小或实际instances友好的场景，可用branch-and-bound、meet-in-the-middle、dynamic programming、SAT/ILP encoding与constraint propagation。它们保留correctness和optimality，但worst case仍exponential。

工程上应记录timeout、incumbent solution、lower bound和optimality gap；超时不能伪装成“无解”。

放松optimality：approximation与heuristics

Approximation algorithm在polynomial time给provable ratio。Minimization返回C，若：

C\le \rho\cdot OPT

则是rho-approximation。Heuristic可能表现好但无worst-case ratio，两者不能混称。

Lower bound必须valid，否则ratio没有certificate。Metric TSP有structure-dependent approximation；general TSP在缺乏triangle inequality时难以近似。

Randomized local search、simulated annealing和genetic algorithms可产生high-quality candidates，但报告应分清empirical quality、probability guarantee和deterministic bound。

放松generality：特殊结构与参数化

若points都在circle boundary，optimal TSP按cyclic order访问；bounded treewidth、planarity、small integer weights或small parameter k也可能带来exact algorithms。

Fixed-parameter tractability把time写成：

f(k)\,n^c

Exponent c与k无关。即使f(k) exponential，只要domain保证k小，仍可形成可靠工程边界。Promise必须在入口验证，不能把general instance误送special solver。

6.6.13 Unknown frontier与不能过度推断的结论

Natural NP problems多数已分类为P或NP-complete，但仍有重要frontier。Factoring长期不知是否在P，也不认为已知NP-complete；若P不等于NP，Ladner theorem保证NP中存在neither P nor NP-complete的problems。

3-SUM存在quadratic algorithm，但是否有truly subquadratic algorithm是fine-grained complexity问题。这里“hard”相对的是 $n^{2-\epsilon}$ threshold，而非P versus NP。

Undecidable problems如halting problem不属于NP-complete：NP problems至少decidable并有polynomial certificates。Complexity讨论“需要多少资源”，computability先问“是否存在总会停机的algorithm”。

Cryptography也利用believed hardness，但security需要average-case、adversarial和parameter assumptions，不能仅凭worst-case NP-hardness推出实际安全。

6.6.14 Independent complexity certificate

一份可复查的classification proof应列出：

Exact problem form：decision/search/optimization。
Encoding与input length。
YES certificate representation及size polynomial。
Verifier logic及time polynomial。
Reduction source、target、map和size growth。
YES if and only if YES的双向correctness proof。
结论依赖的assumptions，例如P不等于NP。

对solver本身，还要分别报告worst-case class、instance distribution、timeout behavior、approximation ratio、observed quality与certificate。Theory不是替代benchmark，而是规定benchmark不能证明什么。

6.6.15 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“6.6 · Intractability”的两个最小情境间切换，再逐项选择正式概念。预测“若 A ≤p B 且 B 有多项式算法，则 A 也有多项式算法；困难性证明使用相反推论方向”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

6.6 · Intractability：对象、操作与不变量

区分 P、NP、NP-hard 与 NP-complete，并用多项式归约和证书验证指导工程取舍

选择最小情境

切换正式概念

证书验证: 给定 Hamilton 回路候选顶点序列
当前观察: intractability：在线性或多项式时间检查每点一次及相邻边存在

若 A ≤p B 且 B 有多项式算法，则 A 也有多项式算法；困难性证明使用相反推论方向

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

难解性：在实验 1 中指出对应状态，并写出一个通过条件。
计算复杂性：在实验 2 中指出对应状态，并写出一个通过条件。
多项式时间：在实验 3 中指出对应状态，并写出一个通过条件。
P与NP：在实验 1 中指出对应状态，并写出一个通过条件。
NP完全性：在实验 2 中指出对应状态，并写出一个通过条件。
应对难解问题：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“若 A ≤p B 且 B 有多项式算法，则 A 也有多项式算法；困难性证明使用相反推论方向”不是孤立结论？

选择“证书验证”的输入：给定 Hamilton 回路候选顶点序列。按定义判定问题 → 写出证书验证器 → 选择已知困难源问题 → 构造多项式归约 → 核对方向与工程策略保存状态，并用“在线性或多项式时间检查每点一次及相邻边存在”核对方向；随后只改变一个变量，检查公式的前提和边界是否仍成立。

问题 3：故障恢复。 怎样证明“从目标难题归约到已知难题却声称目标 NP-hard，或把尚未证明的 P≠NP 当作定理”已经修复？

保存实例编码长度、证书、验证步骤、归约函数、规模界、yes/no 保持与小规模穷举预言机作为正常基线；注入该故障并标记第一个违反“NP 结论必须给出多项式长度证书和多项式验证器；NP-hard 必须保持归约方向”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

小结

Intractability是problem-level resource claim，不是某个implementation暂时慢。
Computational complexity研究all algorithms；结论必须绑定model、encoding与problem form。
Polynomial time是robust tractability surrogate，但不是现实性能的充分条件。
Input size按representation length计算，numeric-value loops可能是pseudo-polynomial或exponential。
P中的problems能polynomial solve；NP中的YES instances有polynomial certificate和verifier。
P and NP是否相等仍未知；NP不代表non-polynomial。
NP-completeness等于in NP加every NP problem reduces to it；NP-hard不要求membership。
Proving new NP-complete problem需要known-complete source reduce to candidate，并独立证明candidate in NP。
TSP decision是NP-complete，optimization是NP-hard；它们仍有exact exponential algorithms。
Coping with intractability要明确放松worst-case time、optimality或arbitrary instances。
Approximation、heuristic、parameterized和special-case algorithms提供不同、不可混淆的guarantees。
Complexity certificate记录encoding、witness、verifier、reduction与assumptions，使分类可独立复查。