《《系列文章》》【统计-计算间隙：归约法的理论与实验】第15章：低度多项式方法实现——计算下界的“预测器“

第15章：低度多项式方法实现——计算下界的"预测器"

知识公有化声明：本章为基于公开教材与论文的独立教学讲义，所有公式为通用形式推导，图表为原创设计，代码为独立实现。

15.1 引言：给算法能力"画一条线"

核心工程问题：前几章我们通过实验"观察"到了统计-计算间隙的存在。但实验只能告诉我们"还没有人找到好的算法"——无法区分"还没发现"和"根本不存在"。低度多项式方法（Low-Degree Polynomial Method）提供了一条精确的可证明边界：它严格刻画了一类广泛的多项式时间算法（包括谱方法、近似消息传递、局部搜索等）的能力上限。

本章将实现低度似然比的计算，预测各问题的计算阈值，并将预测结果与第12-14章的实验进行系统对比。