@@M@@O(2^{0.49n})@@结果族 138：Subset Sum in
@@M@@O(2^{0.49n})@@time · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
超市里 @@M@@n@@ 件商品各标了价：能否挑出一部分，正好凑出目标金额？这个”子集和”问题看似小学生也能试，却是最早的一批 NP 完全问题。五十年来最快的通用解法一直是 1974 年的”折半搜索”，指数死死停在 @@M@@2^{n/2}@@：中间只有些省多项式因子的零头改进，或者只对”随机题目”有效的招数。这篇论文对最坏情形的任意输入，终于把指数撬到 @@M@@2^{0.49n}@@。
关键词卡片
@@M@@n@@ 个整数里挑子集凑目标，1972 年就入选 NP 完全问题。@@M@@2^{n/2}@@ 张表再对账，1974 年至今的标杆。@@M@@|V|-\log|\Sigma(V)|@@，决定走哪条算法分支。@@M@@P@@ 的带相位求和，用傅里叶反演数解。看个具体例子
公式卡——定理代入 @@M@@n=10^4@@：旧法约 @@M@@2^{5000}@@ 步，新法 @@M@@\le C\cdot 2^{4900}@@ 步，省下约 @@M@@2^{100}\approx 10^{30}@@ 倍工作量。新算法是单一程序、掷硬币辅助的随机算法：对输入没有任何分布假设，允许可重复的整数，多项式比特长度以内通吃；时间界对每一次随机执行（包括答错的那次）都成立，答对概率至少 @@M@@2/3@@。
为什么值得关心
五十余年来子集和的精确指数首次跌破 @@M@@1/2@@，宣告 @@M@@2^{n/2}@@ 不是终点，也重新点燃了”NP 完全问题的精确指数还能压多低”这场竞赛。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的场景是超市挑货凑金额。换成半数学的说法：对象是 @@M@@n@@ 个正整数和一个目标数 @@M@@t@@；要判断的命题是”存在某个子集，其元素之和恰好等于 @@M@@t@@“。经典的操作策略是折半：把物品分两半，各半枚举全部子和（各 @@M@@2^{n/2}@@ 种）并列表，再在两表间查互补对。五十年来的事实是：任何最坏情形算法的耗时指数都钉在 @@M@@2^{n/2}@@。要问的量是：这个指数常数能否被撬动。
第二级台阶
用本科术语精确化。折半搜索（meet-in-the-middle）指 Horowitz–Sahni（1974）的两表互补法，是 NP 完全问题”精确指数算法”的基准线。亏格度量 @@M@@d(V)=|V|-\log|\Sigma(V)|@@ 描述一组整数之子集和”撞车塌缩”的程度（@@M@@\Sigma(V)@@ 为不同子和的集合），亏格大意味着列表可以预先截短。隔离引理（Mulmuley–Vazirani–Vazirani 1987）说：给元素加随机平局权重后，若有解则以恒定概率存在某个目标值恰被一个子集命中。模 @@M@@P@@ 校验和指对素数 @@M@@P@@ 的带相位子和 @@M@@\sum_I e_P(\sum_{i\in I}\phi_i)@@，可用傅里叶反演估计。
第三级台阶
主定理在此语境下陈述：存在单一的一致随机算法，在字长 @@M@@O(n+b)@@ 的字 RAM 上，对每个固定多项式比特界 @@M@@b\le n^c@@，一切足够大的 @@M@@n@@ 上每次随机执行（包括答错的那次）都不超过 @@M@@C_c\,2^{0.49n}@@ 次字操作，答对概率至少 @@M@@2/3@@。假设各自挡住一种退化：多项式比特长度排除数值天文级的伪多项式场景；”时间界对每次执行成立”排除只对平均耗时负责的弱声明；对输入无分布假设、允许重复整数，则堵住”只对随机实例有效”的批评。结论即：折半搜索五十年不动摇的指数常数首次被压破 @@M@@1/2@@。
论文构造了一致随机经典算法，最坏情形下以 @@M@@O(2^{0.49n})@@ 字操作求解任意多项式比特长度的子集和问题（Subset Sum），首次把折半搜索 50 余年来停留在 @@M@@2^{n/2}@@ 的指数常数压到 @@M@@1/2@@ 以下，且时间界对每次执行都成立。
子集和问题：给定 @@M@@n@@ 个正整数 @@M@@a_1,\dots,a_n@@ 与目标 @@M@@t@@，问是否存在子集 @@M@@I@@ 使 @@M@@\sum_{i\in I}a_i=t@@。它是 Karp 1972 年 NP 完全列表中的背包问题（Knapsack）。Horowitz–Sahni 1974 年的折半搜索（meet-in-the-middle）给出 @@M@@2^{n/2}@@ 时间；Schroeppel–Shamir 1981 年保持该时间把空间降到 @@M@@2^{n/4}@@；Chen–Jin–Randolph–Servedio（2023）得到 @@M@@O(2^{n/2}n^{-\gamma})@@ 的多项式因子改进。但把指数常数压破 @@M@@1/2@@，最坏情形下此前无人做到：伪多项式（pseudopolynomial）算法按目标数值 @@M@@t@@ 计量，而多项式比特长度下 @@M@@t@@ 可极大；表示方法（representation method，Howgrave-Graham–Joux 一系）只对随机实例有效。本文在字 RAM（word-RAM）模型上攻克了这一目标。
定理（主定理）：存在单一的一致（uniform）随机算法 @@M@@\mathcal A@@：对每个 @@M@@n\ge 2@@ 的输入，它在每次随机执行上都停机，并以至少 @@M@@2/3@@ 概率输出正确答案；对每个固定的多项式比特界 @@M@@b\le n^c@@（@@M@@b@@ 为输入整数最大比特长度），所有足够大的 @@M@@n@@ 上每次执行（包括答错的执行）用时均不超过 @@M@@C_c\,2^{0.49n}@@ 次字操作。程序不依赖 @@M@@c@@、无需外部建议（advice）；中间界为 @@M@@2^{0.489995n}\operatorname{poly}(n+b+2)@@，靠指数空隙吸收多项式因子。对输入无分布假设，允许重复整数；字长为 @@M@@O(n+b)@@。
全文围绕恒等式：精确桶的带相位和 = 模 @@M@@P@@ 桶的带相位和 − 别名（alias，模 @@M@@P@@ 相等但整数不等的假阳性子集）的相位之和。先隔离：用随机平局权重 @@M@@u_i@@ 构造 @@M@@c_i=Ca_i+u_i@@、@@M@@t_s=Ct+s@@，隔离引理（Isolation Lemma）保证有解时以概率 @@M@@\ge 11/12@@ 存在恰含一个解的 @@M@@t_s@@，最终只需分辨校验和是 @@M@@0@@ 还是 @@M@@1@@，绕开反集中（anti-concentration）估计。再二分：定义亏格（deficiency）@@M@@d(V)=|V|-\log|\Sigma(V)|@@（@@M@@\Sigma(V)@@ 为不同子和集），若随机半集期望亏格超过 @@M@@0.01004n@@，Chebyshev 说明两侧不同子和均 @@M@@\le 2^{0.489985n}@@，带帽（capped）折半搜索直接判明实例；否则进入低亏格情形。核心是模和校验和估计（modular checksum estimation）：取素数 @@M@@P\approx 2^{0.51772n}@@ 与随机相位 @@M@@\phi_i@@，Fourier 反演给出 @@M@@V_\rho=\frac1P\sum_k J_\rho(k)@@，但均匀频率采样的二阶矩达 @@M@@2^n@@，不可行；于是把频率 @@M@@k=hL+\ell@@ 拆成高低位，用随机块表（标签为 @@M@@*@@ 或均匀移位）与对数密度得分做非对称过滤（asymmetric filtering），”匹配”是同一张整表下同时过关的高低条目，似然比测度变换加按块粗化的”模式”（pattern，仅 @@M@@2^{O(\sqrt n)}@@ 个）既覆盖所有频率又把列表压在 @@M@@2^{\tau n}@@（@@M@@\tau=0.48996@@）内；匹配少的模式用逆重数加权的重要性采样（importance sampling），均方误差由两条圆上密度不等式（附录数值求积证明）压到 @@M@@\le 2^{-0.0007n}@@。然后是别名提取（alias extraction）：给每个子集多种”两记录 + 共享块掩码”表示，随机翻转 @@M@@F@@ 使 @@M@@J=I\triangle F@@ 均匀，用小模数过滤；关键创新是精确整数排除规则——被访问的记录对必有非零整数差异，随机素数碰撞（random-prime collision）引理把期望访问对数压到 @@M@@2^{0.48988n}@@；覆盖论证用低亏格保证某大小 @@M@@m\approx0.0567n@@ 的块上有 @@M@@\ge 2^{0.4894m}@@ 个不同带符号权和，单次试验命中概率 @@M@@\ge n^{-4}@@，@@M@@n^{10}@@ 次试验后联合覆盖全部别名。最后实现层用带拒绝上限的有限抽样与列表硬帽，使时间界对每次执行成立。
本结果暂无形式化证明：两条关键滤波不等式（如 @@M@@0.5169<0.51772@@ 的指数预算）由附录数值求积与有理包围验证，常数留有显式空隙，但整体论证仍应以社区核验为准。同族姊妹篇沿同一路线把空间压到 @@M@@O(2^{n/5})@@，两文在折半搜索与亏格分析上互相印证。按 OpenAI 官方声明，未经形式化的结果可能有问题，引用前请留意后续核验进展。
问 1：整个论证的支点恒等式是什么，哪一侧最难算？
答：支点是式 (1)（overview-subtraction）：精确桶的带相位和 = 模 @@M@@P@@ 桶的带相位和 − 别名的相位之和。模和 @@M@@V_{t'}=\frac1P\sum_k J_{t'}(k)@@ 的朴素频率采样二阶矩是 @@M@@\E_\phi|J_{t'}(k)|^2=2^n@@，直接超标；论文被迫发明”高低位拆分 + 模式分组 + 逆重数重要性采样”的整套非对称滤波，把列表压进 @@M@@2^{\tau n}@@（@@M@@\tau=0.48996@@）。最脆的是覆盖论证：必须证明每个频率都出现在自己模式的匹配里，漏掉任一频率，@@M@@V_{t'}@@ 的估计就系统性偏移。
问 2：为什么必须做隔离（isolation），不隔离行不行？
答：不隔离就得直接估计”多解时若干相位之和”的大小，需要反集中型估计——引言明说隔离”removes any need for a separate anti-concentration theorem”。隔离后只需分辨校验和是 @@M@@0@@ 还是模长 @@M@@1@@ 的单相位，误差阈值 @@M@@1/4@@ 对 @@M@@1/2@@ 即可判定。用平局权重 @@M@@u_i@@ 构造 @@M@@c_i=Ca_i+u_i@@ 后，隔离引理保证概率 @@M@@\ge 11/12@@ 存在唯一解目标。
问 3：别名提取里”精确整数排除规则”为什么是关键创新？
答：被枚举的记录对若满足精确整数方程就被跳过（包括掩码重叠的对），于是留下的每对都有非零整数差异，随机素数碰撞引理据此把期望访问对数压到 @@M@@2^{0.48988n}@@；掩码不相交的检查只在这有界枚举之后做。若反过来先查掩码，坏对没有整数差异可借力，计数会失控。这一步与 Randolph–Węgrzycki 的兼容证书目的不同——这里是为了列假阳性以便减掉。
问 4：与已有工作相比真正的新意是什么？
答：方向上的区别清楚：伪多项式（Bringmann、Koiliaris–Xu、Chan 2026）按 @@M@@t@@ 计量，多项式比特长度下失效；表示方法（HGJ、BCJ、AKKN）只对随机实例有保证；CJRS 2023 是 @@M@@2^{n/2}n^{-\gamma}@@ 的多项式因子节省，论文引言明确这与”压低指数常数是不同目标”。本文是第一个对最坏情形任意输入把指数压破 @@M@@1/2@@ 的（随机）算法。
问 5：AI 生成这类算法分析最可能在哪里出错？
答：数值常数链。@@M@@P\approx 2^{0.51772n}@@、@@M@@0.5169<0.51772@@ 的滤波预算、两条圆上密度不等式（附录用有理包围与解析求积证明）、覆盖概率 @@M@@n^{-4}@@、@@M@@n^{10}@@ 次试验——这些常数首尾相扣，任何一处实际略差于声称值，0.49 就保不住。这正是最需要形式化或独立复算的部分，而目前没有。
问 6：”时间界对每次执行成立”这个不寻常的声明如何实现，为何要强调？
答：实现层（第 6 节）用带拒绝上限的有限随机抽样与列表硬帽，把尾风险转化为确定性截断；程序是单一有限程序、无 advice、@@M@@c@@ 不可见，靠中间界 @@M@@2^{0.489995n}\operatorname{poly}(n+b)@@ 的指数空隙吸收多项式因子。强调它是因为多数随机算法只承诺期望或高概率耗时，”答错的那次也要快”是更强的模型诚实性，也是可复现性的卖点。
问 7：谁会用到它？
答：精确指数算法社区与密码分析界（子集和是后量子背包密码的底层问题）。0.49 本身不构成对现有密码的威胁（安全参数照旧），但它宣告 @@M@@2^{n/2}@@ 不是壁垒，预期会刺激 KNAPSACK、最近向量等邻近问题的指数竞赛；同族姊妹篇沿同一路线把空间压到 @@M@@O(2^{n/5})@@。
总评
这是五十年来子集和精确指数的首次实质突破，方法（隔离 + 模校验和 + 别名提取）自成一格且可迁移；最大风险集中在由数值求积支撑的常数链条上——未经形式化验证，0.49 与 0.5 之间那 0.01 的生存空间全系于几个小数点后第五位的正确性。