学习困难性的归约

学习器接收的是随机样本而不是一个显式目标实例，所以归约必须把困难信息放进可高效采样、且具有可检测风险质量的区域。信息若只藏在指数小概率事件中，低风险预测器完全可以忽略它；输出若不保留可解码结构，低风险也未必给出源问题见证。

SAT 到 proper 学习的具体模板 ​

给定含 $m$ 个子句的 CNF 公式 $\mathrm{\Phi }$，把实例空间取为这些子句，令每个赋值 $a$ 表示一个假设

在 $\mathrm{\Phi }$ 可满足时，取一个满足赋值作目标概念，并让 $D_{\mathrm{\Phi }}$ 在 $m$ 个子句上均匀分布；归约能高效抽取随机子句及其标签 $1$。假设存在输出仍属于 $\{h_a\}$ 的高效 proper learner，以精度 $\epsilon <1/m$ 学习这批全正样本，那么低于 $1/m$ 的总体错误率迫使它在每个子句上都输出 $1$，对应的赋值就是 $\mathrm{\Phi }$ 的满足见证。公式不可满足时，没有 proper 输出能通过逐子句验证。因此这样的 learner 会给出 SAT 的随机化多项式时间求解路径，困难性结论须明确写成相应的复杂度假设，例如 $\mathrm{NP}⊈\mathrm{RP}$。

这个构造同时暴露表示与输出类为何不能省略。若允许完全 unrestricted 的 improper learner，常数函数 $h(C)\equiv 1$ 对该分布零错误，却不编码任何共同满足所有子句的赋值；归约随即失效。要排除 improper learner，必须另造能从任意低风险输出解码见证的表示保持归约，而不是把 ERM 或 proper 困难性换个标题。

关键辨析 ​

证明某类 ERM 是 NP-hard，只排除了“精确求这个经验最优”的路径。improper learner 可能输出类外预测器，近似或非 ERM 算法也可能绕开该优化问题，所以不能据此直接宣布该类不可高效 PAC 学习。反过来，密码学困难性常依平均情形或伪随机假设，必须明确复杂度假设，不能模糊写成“除非 P=NP”。

多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。提供复杂度传递语言；本页增加学习专有的分布接口、风险量词和表示约束。统计与计算复杂度公理库学习的统计复杂度与计算复杂度Statistical-computational complexity of learning分开衡量数据量、求解代价和输出表示，避免把统计可学误读为计算可解。的分离正是这些归约要保护的对象。

proper ERM 的 NP-hardness、improper 学习困难性和密码学平均情形下界是三种不同结论。要从前者走向后两者，必须分别排除类外输出与非 ERM 算法，或建立能从任意低风险预测器解码见证的更强归约。

归约模板也用于证明弱学习、统计查询和噪声容忍的限制；每种模型都要显式模拟其 oracle，并把精度与置信参数纳入总运行时间。只给一个概念类映射而没有可采样分布和 gap，不构成完整学习归约。