学习困难性的归约

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

SAT 到 proper 学习的具体模板 ​

对 $N$ 个布尔变量，固定实例域为这些变量上的所有子句。每个赋值 $a\in \{0,1{\}}^N$ 定义

并规定 $h_a$ 的输出描述就是赋值 $a$，因此可直接求值和验证。输入 CNF 公式 $\mathrm{\Phi }$ 只决定采样分布：在它的 $m\ge 1$ 个子句记录上均匀取一条并标注为 $1$。若 $m=0$，直接判可满足。

当 $\mathrm{\Phi }$ 可满足时，某个满足赋值实现了这些标签，而归约无需知道它就能模拟样本。调用假设中的高效 proper learner，取 $\epsilon =1/(2m)$、$\delta =1/3$。成功时，若输出赋值错过任一子句，其风险至少为 $1/m$，与风险至多 $1/(2m)$ 矛盾；所以该赋值满足全部子句。

运行时使用学习器承诺的多项式时限，并拒绝超时或格式不符的输出，最后逐子句验证赋值。不可满足时，任何输出都不能通过验证，即使这时样本不满足 learner 的可实现前提；可满足时，按其保证至少以 $2/3$ 概率接受。这给出 SAT 的 RP 算法，故在 $\mathrm{NP}⊈\mathrm{RP}$ 的假设下排除这种指定表示的高效 proper learner。固定输出编码很重要：只知道预测函数在语义上等于某个 $h_a$，未必能高效提取对应赋值。

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

关键辨析 ​

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

与一次性 many-one 变换相比，这里的归约还要说明随机样本接口、风险量词、子程序时限和输出解码。统计与计算复杂度理路学习的统计复杂度与计算复杂度Statistical-computational complexity of learning分开衡量数据量、求解代价和输出表示，避免把统计可学误读为计算可解。的分离正是这些归约要保护的对象。

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

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