从“目标枢纽”开始
设想一个目标判定问题 H，你会先听到这么一句：
如果 H 是 NP-hard，那么 NP 中的每个可高效检查的问题都应以多项式时间归约到 H。
这不是“一个问题”变硬的问题，而是所有 NP 问题都指向一个目标的问题。
先看中心点：H 接收来自多个 NP 源问题的归约这些箭头是定义前提，不是已经构造完成的归约。它们表示 NP-hardness 所要求的比较关系。判定问题 L源实例 x答案保持
要求的映射L <=p H每个源判定实例都要能这样映射当前未构造
H目标判定问题问题：给定 y，是否 y ∈ H？
电路满足性判定（Circuit-SAT）一个小电路 C 与赋值 101目标形式: f_CircuitSAT(C)要求: x ∈ L ↔ f(x) ∈ H源 Yes → 目标 Yes
SAT公式 φ = (x1 OR x2) ∧ (¬x1 OR x3)目标形式: f_SAT(φ)要求: x ∈ L ↔ f(x) ∈ H源 Yes → 目标 Yes
团（Clique）图 G 中存在大小为 3 的团目标形式: f_Clique(G, 3)要求: x ∈ L ↔ f(x) ∈ H源 Yes → 目标 Yes
独立集（Independent Set）图 G 和 k=4，但不存在大小为 4 的独立集目标形式: f_IS(G, 4)要求: x ∈ L ↔ f(x) ∈ H源 No → 目标 No
任意 L ∈ NP抽象源实例 x∀L∈NP 的形式占位仅符号化
本页的结论是条件定义目标；任何行都不代表某个真实完成的困难性证明。
上图强调：每条箭头是定义所要求的翻译承诺，不等于某个具体困难性证明已经完成。
第一个朴素直觉
“难”很容易被误解成：
- 一个输入很大就难。
- 候选很多就难。
- 目前没有快算法就难。
这些都能给你研究动机，但不足以定义 NP-hard。
一个大输入就代表困难一个看起来很大很大的输入就是困难。困难性不是单个输入大小。它是关于问题族和归约可比关系。
候选太多如果暴力枚举候选很多，那么它就 NP-hard。找不到快算法还没找到快速算法就能证明 NP-hard。
为什么会坏掉
NP-hardness 看的是比较关系。一个单独归约只是具体例子，不是定义。
单次归约只是一条线索，不是定义NP-hardness 需要 NP 中每个源问题都能归约到 H，而不是一个最爱源。错误目标视图A <=p H只有一个源问题
缺失其他源问题这能显示一个例子归约，不足以证明 NP-hardness。
NP-hardness 需要的视图L1 <=p HL2 <=p H..., 对每个 L in NP完整族要求
单源视图失败点不能推出 H 包含全部 NP 问题。不能对任意 L 触发 P=NP 的条件推理。
所以“一条箭头”是“示例来源”，不是“全量来源”。
核心发明：对所有源的全称量化
NP-hardness 的形式是：
H is NP-hard⟺∀L∈NP,L≤pH.
保真约束是：
x∈L⟺fL(x)∈H
每一条源都要有双向保持：Yes 与 No 都要保留。
账本：保持 Yes 与 No归约对实例 x 有效时，目标 f(x) 的真假值必须保持一致。是实例（Yes）一个小电路 C 与赋值 101ff_CircuitSAT(C)
目标（Yes）目标答案: 是 否实例（No）图 G 和 k=4，但不存在大小为 4 的独立集ff_IS(G, 4)
目标（No）目标答案: 否 是与否两个示例都采用同一类归约形式并保持真假值一致。
全称量词展开为许多必须的源问题承诺每一行都是在同一个目标 H 下的一条实例保持约束。电路满足性判定（Circuit-SAT）一个小电路 C 与赋值 101源 = 是目标形式: f_CircuitSAT(C)目标 = 是当且仅当（iff）: x ∈ L ↔ f_L(x) ∈ H
SAT公式 φ = (x1 OR x2) ∧ (¬x1 OR x3)源 = 是目标形式: f_SAT(φ)目标 = 是当且仅当（iff）: x ∈ L ↔ f_L(x) ∈ H
团（Clique）图 G 中存在大小为 3 的团源 = 是目标形式: f_Clique(G, 3)目标 = 是当且仅当（iff）: x ∈ L ↔ f_L(x) ∈ H
独立集（Independent Set）图 G 和 k=4，但不存在大小为 4 的独立集源 = 否目标形式: f_IS(G, 4)目标 = 否当且仅当（iff）: x ∈ L ↔ f_L(x) ∈ H
任意 L ∈ NP抽象源实例 x源 = 符号化目标形式: f_L(x)目标 = 符号化当且仅当（iff）: x ∈ L ↔ f_L(x) ∈ H
传递桥：后续证明怎么用
后续我们拿到已知 NP-hard 的源问题 A 后，不必每次都重画所有源；只要证明：
∀L∈NP,L≤pA
和
A≤pH
然后即可推出
∀L∈NP,L≤pH.
这就是为什么后续多数学科证明会走“已知困难源 + 一步桥接”路线。
实操中的传递性桥梁后续证明通常先拿到一个已知 NP-hard 的 A，再证明 A <=p H。已知前提∀ L in NP, L <=p A这给 A 一个完整的 NP 覆盖。
A <=p H需证明的单条传递事实
合成结论∀ L in NP, L <=p H实操中不必再次重画所有源问题。
求解器推理管道
条件化地理解：如果假设 H ∈ P，那么对每个能有效归约到 H 的源问题 L，也能在 P 中求解它。
function solveL(x: L) {
const y = reduceLtoH(x); // f_L(x)
return solveH(y); // 假设在多项式时间内可算
}
选择源问题选中源问题 电路满足性判定（Circuit-SAT） 作为当前的 L。Circuit-SAT 示例源问题
接收源实例接收 Circuit-SAT 的实例 x。源: 是
归约到 H构造并输出 f_CircuitSAT(C)。若定义前提成立，这一步对该源问题是有效的。目标: 是
调用 solveH假设 H 的判定器是多项式时间的。对翻译后的目标实例调用该判定器。目标: 是假设: solveH ∈ P
返回源答案返回与目标实例相同的 Yes/No。保持性意味着这就是原始源实例的正确答案。源: 是目标: 是
选中源问题 电路满足性判定（Circuit-SAT） 作为当前的 L。
选择源问题选中源问题 电路满足性判定（Circuit-SAT） 作为当前的 L。
接收源实例接收 Circuit-SAT 的实例 x。
归约到 H构造并输出 f_CircuitSAT(C)。若定义前提成立，这一步对该源问题是有效的。
调用 solveH假设 H 的判定器是多项式时间的。对翻译后的目标实例调用该判定器。
返回源答案返回与目标实例相同的 Yes/No。保持性意味着这就是原始源实例的正确答案。
正确性直觉
最后一步靠的是“保持”契约：
- 源实例是 Yes，则
x in L，所以 f_L(x) in H，目标求解器返回 Yes；
- 源实例是 No，则
x notin L，所以 f_L(x) notin H，目标求解器返回 No。
因此只有在双向保持下，返回目标答案才正确。
复杂度后果
推理公式是：
(∀L∈NP,L≤pH)∧(H∈P)⟹NP⊆P.
结合 P ⊆ NP（来自 P 与 NP）可得：
P⊆NPandNP⊆P⟹P=NP.
这是条件命题：它不说明 P ≠ NP，只是说“若某个 NP-hard 的 H 落在 P，则会发生类崩塌”。
复杂度组合堆栈归约成本与 H 求解成本相加，仍是多项式。| 符号 | 表达式 | 含义 |
|---|
| m | m <= n^b | 目标规模上界 |
| Treduce(n) | O(n^a) | 将源实例翻译为 H 实例 |
| TsolveH(m) | O(m^c) | 在 H 上多项式求解 |
| Ttotal(n) | O(n^a + n^{bc}) | 组合流水线 |
源规模符号: n目标规模符号: m组合: O(n^a + n^{bc})
可选具体示例n = 12Treduce(n) = O(12^a)m <= (12)^bTsolveH(m) = O((12^b)^c)Ttotal(n) = O(12^a) + O((12^b)^c)
NP-hard、in NP、NP-complete 的区别
NP-hardness 是与所有 NP 问题比较的关系，不自动给出 in NP。
NP-hard 只说比较方向；NP-hard 且在 NP 里时是 NP-complete；- 优化任务在本节点不直接作为对象；通常先转成决策版本。
仅 NP-hardin NP: 否 · NP-hard: 是 · NP-complete: 否困难性比较的是 NP 全家族，不保证问题本身在 NP 里。这是可能关系，留到后续节点再给具体例子。仅 in NPin NP: 是 · NP-hard: 否 · NP-complete: 否有高效验证证书，但还没有“所有 NP 都归约过去”的证据。许多验证型问题在 NP，但还不知道它们 NP-hard。NP-完全in NP: 是 · NP-hard: 是 · NP-complete: 是既在 NP 中也 NP-hard。这是最熟悉的“既困难又可验证”类别。
常见误区
困难性方向反了结论: 反例：`H <=p L` 不能证明 `H` 是 NP-hard。H <=p L 不足以证明 H 是 NP-hard。
`H <=p L` 的箭头方向是反的；困难性要求 NP 中每个 L 都要归约到 H。
这个方向只是 `H` 到 `L` 的归约，因此有了 `L` 的求解器才可能帮助求解 `H`，不是反过来。
只用一个源问题不足以证明统一困难性展开并看为什么不对NP-hard 不代表在 NP 中展开并看为什么不对把“某个大实例很难”当成困难性展开并看为什么不对“目前没找到快算法”展开并看为什么不对把优化问题直接按判定困难性理解展开并看为什么不对
图谱连接
本节点在局部图中位于：
p-vs-np -> polynomial-time-reductions -> np-hardness.
后续具体 Circuit-SAT 节点会提供首个真实的源问题构造链。
图位置与局部流程这和已有实现边的顺序一致，并预告后续证明对象。p-vs-np判定问题 + P/NP 框架
->前置关系
polynomial-time-reductions判定归约
->前置关系
np-hardness通用目标定义
->后续预览
circuit-sat首个具体源问题节点（未链接）
练习
若要判断“`H` 是 NP-hard”，哪种箭头方向是对的？选择一个答案以检查此题。
一个 A <=p H 就足以说明 H NP-hard。选择一个答案以检查此题。
下面哪一类与这种情况一致？in NP 与 NP-hard 都为真。选择一个答案以检查此题。
假设 H ∈ P 且 SAT 有效归约到 H。对 SAT 来说这个推论说什么？选择一个答案以检查此题。
- 选择正确箭头方向。
- 为什么只用一个源问题不够？
- 哪个类同时为
in NP 与 NP-hard？
H ∈ P 时，源问题会得到什么含义？
图谱连接 : NP-Hardness
