结果族 138：Subset Sum in
@@M@@O(2^{0.49n})@@time · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
还是子集和，但换了个比法：时间维持五十年标杆 @@M@@2^{n/2}@@ 不动，专门比谁”内存抠”。旧方法相当于把半本电话簿整个背下来，新算法像按需翻页检索，把工作内存压到 @@M@@2^{n/5}@@ 个字。
关键词卡片
@@M@@2^{n/4}@@。@@M@@\ge 2/3@@ 概率接受。看个具体例子
空间指数的四级台阶：1974 年 @@M@@0.5@@ → 1981 年 @@M@@0.25@@ → 2024 年 @@M@@0.246@@ → 本文 @@M@@0.199@@（即 @@M@@O(2^{n/5})@@ 个字）。代入 @@M@@n=100@@：内存从折半搜索的 @@M@@2^{50}@@ 字降到约 @@M@@2^{20}@@ 字，差约十亿倍。同时时间稳稳保持在 @@M@@\operatorname{poly}(n)\cdot 2^{n/2}@@，时间与空间界对每次执行（包括失败的那次）同时成立；算法是单一程序，任意多项式比特长度的输入通用，错误单侧——绝不把无解误报成有解。
为什么值得关心
“生成信息与存储信息之别”是时空权衡四十余年的主线，本文立下普通意义（不藏多项式因子、每次执行都算数）的新空间纪录，并与姊妹篇的破指数算法共享亏格分析、互相印证。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的对比是”背下半本电话簿”与”按需翻页检索”。换成半数学的说法：对象仍是那道子集和判定题——@@M@@n@@ 个正整数、一个目标，问有没有子集恰好凑中；经典解法把一半物品的全部子和列成一张大表存放，再拿另一半逐个到表里对账。时间与内存都停在 @@M@@2^{n/2}@@。论文换掉的只有一件东西：表不再整个存下，而是按需流式生成、按桶取用；时间维持原尺度，专门把”同时要记着的字数”压下去。
第二级台阶
用本科术语精确化。折半搜索（Horowitz–Sahni 1974）用 @@M@@2^{n/2}@@ 时间与空间；Schroeppel–Shamir（1981）用四条小列表按序生成大列表，空间降到 @@M@@O^*(2^{n/4})@@，确立了”生成信息与存储信息之别”。亏格 @@M@@d(V)=|V|-\log_2 N(V)@@（@@M@@N(V)@@ 为不同子和个数）度量子和的撞车塌缩：亏格大则列表天然短，亏格小则给”表示法”提供充足的互异权重。表示法（representation method）把一个解拆成许多”双亲—孩子”分解，靠多重性在模数滤波下保住幸存副本。单侧错误指：无解时绝不误报，有解时以至少 @@M@@2/3@@ 概率接受。
第三级台阶
定理（thm:main）在此语境下陈述：存在单一的一致经典随机算法，在字长 @@M@@O(n+b)@@ 的字 RAM 上，对每个固定多项式比特界 @@M@@b\le n^c@@，每次随机执行（包括失败的那次）至多用 @@M@@A_c n^{k_c}2^{n/2}@@ 次操作与 @@M@@A_c(n+b+2)^{15}2^{0.199n}@@ 个可写字，算法不依赖 @@M@@c@@；每个可写寄存器、计数器与保留的随机数都计入空间，读-only 输入与固定程序不计。假设挡住的退化：多项式比特约定排除数值无界的输入类；”普通意义”计费（不藏多项式因子、无 advice、无随机预言机）排除靠外部存储作弊的弱声明。取 @@M@@\rho>0.199@@ 吸收多项式因子即得普通 @@M@@O(2^{n/5})@@ 空间——空间指数从 1981 年的 @@M@@1/4@@ 台阶再落到 @@M@@1/5@@。
论文给出最坏情形子集和（Subset Sum）的一致随机判定算法：在 @@M@@\operatorname{poly}(n)2^{n/2}@@ 时间下把工作空间压到普通意义 @@M@@O(2^{n/5})@@ 个字（此前最好为 @@M@@O^*(2^{0.246n})@@），时间与空间界对每次执行同时成立，错误单侧，且适用于任意多项式比特长度的输入。
折半搜索（meet-in-the-middle，Horowitz–Sahni 1974）在 @@M@@2^{n/2}@@ 时间内求解子集和，但也要 @@M@@2^{n/2}@@ 空间。Schroeppel–Shamir（1981）用四条小列表按序生成大列表，把空间降到 @@M@@O^*(2^{n/4})@@，确立了”生成信息与存储信息之别”这一时空权衡主线。此后 Nederlof–Węgrzycki（2021）以表示方法（representation method）把空间降到 @@M@@O^*(2^{0.249999n})@@，Belova–Chukhin–Kulikov–Mihajlin（2024）再降到 @@M@@O^*(2^{0.246n})@@（限于数值 @@M@@2^{O(n)}@@ 的输入）。问题在于：在 @@M@@2^{n/2}@@ 时间尺度下空间指数还能压多低？本文给出普通意义（不隐藏多项式因子、每个可写计数器与保留随机数都计入空间）的 @@M@@O(2^{n/5})@@ 字空间界。
定理：存在单一的一致经典随机算法：绝不误答 YES（单侧错误，one-sided error），对每个可解实例以至少 @@M@@2/3@@ 概率接受。对每个固定多项式比特界 @@M@@b\le n^c@@，存在常数 @@M@@A_c,k_c,N_c@@，使得 @@M@@n\ge N_c@@ 时每次随机执行（包括失败执行）至多用 @@M@@A_c n^{k_c}2^{n/2}@@ 次操作与 @@M@@A_c(n+b+2)^{15}2^{0.199n}@@ 个可写字（字长 @@M@@O(n+b)@@）；算法不依赖 @@M@@c@@。推论：取 @@M@@\rho>0.199@@ 吸收多项式因子，得普通 @@M@@O_c(2^{\rho n})@@ 空间，特别地 @@M@@O_c(2^{n/5})@@。
算法按平均亏格（mean deficiency）@@M@@\mu@@ 二分：@@M@@\mathrm d(V)=|V|-\log N(V)@@ 度量不同子和 @@M@@N(V)@@ 的重复度；算法不算 @@M@@\mu@@，每轮同时跑两个试验。试验一（压缩重复和）处理 @@M@@\mu\ge.00765n@@：取 7 个大小 @@M@@s\approx.12n@@ 的随机块，只保留各自的不同子和（上限 @@M@@2^{\lfloor s-.0075n\rfloor}@@，域不相交可忘见证）；再按 Schroeppel–Shamir 的”存储列表 + 生成流”生成四个大组而不存笛卡尔积；随机素数 @@M@@q@@ 把左侧组合按剩余类分桶，一次只装一桶进容量 @@M@@C=2^{\lfloor.199n\rfloor}@@ 的字典，溢出即弃；成功只需解所在桶装得下——异权碰撞期望仅 @@M@@u^3 2^{.1985n+17}=o(C)@@（@@M@@u=n+b+2@@）。试验二（表示法，representation）处理 @@M@@\mu<.00765n@@：取三个大小 @@M@@m\approx.24n@@ 的混合块（mixer），先随机符号翻转 @@M@@F@@（@@M@@t'=t-\sum_{f\in F}a_f@@），解变为均匀子集 @@M@@S\triangle F@@ 而亏格不变；解拆成两个双亲、四个孩子、八条叶子列表，嵌套模数滤波满足 @@M@@p_L\mid p_0@@、@@M@@p_R\mid p_0@@；附加独立素数 @@M@@q@@（additional-prime filtering）再分桶：左侧溢出跳桶，右侧溢出则逐位固定 @@M@@M_0@@ 掩码前缀、在叶子上提前过滤后重新生成；”前缀记账引理”（prefix accounting）按桶数、原始四元组数与相异条目数分别给任务与工作计费，分离生成与存储。幸存分析（survival）先在暴露 @@M@@q@@ 与分离族（separating family）前固定一个表示：平衡、亏格集中与子块计数划分以 @@M@@u^{-3l}@@ 比例保留代表，得 @@M@@|X_i|\ge 2^{L_i}/u^{14}@@ 个不同带符号权；剩余类覆盖（residue coverage）加 Cauchy–Schwarz 给出至少 @@M@@2^{L_i}/u^{16}@@ 个占据剩余类，随机低位依次命中，总幸存概率 @@M@@\ge u^{-100}@@。最终检查是加权不相交性（weighted disjointness）：在 @@M@@M_0@@ 的四个块上采样带仿射偏置（@@M@@\alpha=\log 3@@）的分离集族，固定掩码对覆盖概率 @@M@@\ge 1-4e^{-10}@@；遍历只存小数组，每记录期望工作 @@M@@u^{22}2^{(1-h_*)m}@@（熵界 @@M@@E(k)\le 1-h_*@@ 由凹性证明）。实现层用有界抽样、计数器与字典硬帽落实每次执行的时空界，独立重复放大成功率至 @@M@@2/3@@。
本结果暂无形式化证明。文中的熵与素数估计均为初等显式论证（如 @@M@@h(1/4)<.8114@@ 由 @@M@@3^{53}>2^{84}@@ 推出），但容量余量极紧（碰撞期望指数 @@M@@.1985@@ 对容量指数 @@M@@.199@@），整体仍应以社区核验为准。同族姊妹篇以 @@M@@O(2^{0.49n})@@ 时间压破时间指数 @@M@@1/2@@，本文守住 @@M@@2^{n/2}@@ 时间换取空间指数 @@M@@0.199@@，两文共享亏格二分、随机素数与表示技术。按 OpenAI 官方声明，未经形式化的结果可能有问题，引用前请留意后续核验。
问 1：空间能压到 @@M@@2^{0.199n}@@ 的核心机制是什么，哪里最脆？
答：核心是”生成与存储分离”的前缀记账：附加素数 @@M@@q@@ 把过滤后的双亲分桶，左侧桶溢出直接跳过，右侧溢出则逐位固定 @@M@@M_0@@ 掩码前缀、在叶列表上提前过滤后重新生成，使每个原始四元组在每个前缀深度至多属于一个任务、按深度计费。最脆处有二：一是碰撞预算极紧——异权碰撞期望指数 @@M@@.1985@@（@@M@@+17@@ 常数项）对字典容量指数 @@M@@.199@@，余量只有 @@M@@2^{0.0005n}@@ 量级；二是”每个原始元组恰属一个任务”的计数论证若在某前缀深度漏掉一类被反复处理的元组，时间界先于空间界崩塌。
问 2：为什么时间必须守住 @@M@@2^{n/2}@@，不顺着姊妹篇压到 @@M@@2^{0.49n}@@？
答：这是刻意的交换：姊妹篇用 @@M@@O(2^{0.49n})@@ 时间换空间回到大表存储，本文反其道守住 Schroeppel–Shamir 确立的时间尺度、专攻空间纪录。论文未讨论”时间 @@M@@2^{0.49n}@@ 且空间 @@M@@2^{0.199n}@@“能否同时达成——两条技术路线（模校验和估计 vs 表示幸存）目前并不兼容，这是明显的后续问题。
问 3：算法不算亏格均值，却按均值二分跑两个试验，这为什么合法？
答：正确性不依赖判断哪个分支适用：每轮用新鲜随机性同时跑压缩试验与表示试验，高均值时压缩试验成功、低均值时表示试验成功，二者对每个固定输入都以逆多项式概率（幸存分析给 @@M@@\ge u^{-100}@@）找到解，独立重复放大到 @@M@@2/3@@。这是”猜测并验证”的合法变体，但代价是常数因子翻倍、两套分析的数值预算都要独立过硬。
问 4：与 BCKM 2024 的 @@M@@O^*(2^{0.246n})@@ 相比，真正的新意是什么？
答：三件事：普通意义（ordinary）的空间界——BCKM 藏多项式因子且限数值 @@M@@2^{O(n)}@@ 的输入，本文每个可写字都计费、多项式比特长度通用；时间与空间界对每次执行同时成立；以及组合技术创新：随机符号翻转 @@M@@F@@ 使解均匀化而亏格不变、剩余类覆盖（承 AKKN/NW）配 Cauchy–Schwarz 把互异权重变成占据剩余类、带仿射偏置（@@M@@\alpha=\log 3@@）的加权不相交性终检。附加素数滤波与分离族代价估计直接沿用 BCKM。
问 5：AI 生成这类证明最可能的出错模式是什么？
答：多重嵌套随机对象的条件独立性记账。幸存分析要求在暴露 @@M@@q@@ 与分离族之前固定一个表示，再把表示幸存的失败界无条件扣除、之后才应用后续随机选择——”先固定再暴露”的顺序若在任何一处被颠倒，概率乘法链断裂。加上熵界 @@M@@E(k)\le 1-h_*@@（靠凹性与 @@M@@3^{53}>2^{84}@@ 这类显式有理不等式）、@@M@@\ge u^{-100}@@ 的总幸存概率对 @@M@@u^{22}@@ 之类工作界，全是小常数相乘的窄门。
问 6：单侧错误为什么值得强调，会不会其实没用？
答：有用且非平凡：无解实例绝不误报使算法可作 NO 证书的过滤器使用；实现上靠字典与计数器硬帽，随机性只影响找到解的概率、不允许超预算，这在随机算法中是少见的强保证。但注意它输出的是判定，不重构解 witness——论文未讨论输出解本身的空间代价。
问 7：谁会用到它？
答：精确算法与参数化算法社区（时空权衡、dissection 一脉：FLPS 分离集合、AKKM 随机模归约），以及关心内存受限攻击的密码分析界（背包型后量子方案的安全评估）。空间纪录直接改写”多少台机器/多大内存能跑 @@M@@n@@ 步攻击”的换算表。
总评
这是时空权衡主线上一次实打实的纪录改写（@@M@@1/4\to1/5@@），且以普通意义计费的诚实模型立信；最大风险是 @@M@@0.1985@@ 对 @@M@@0.199@@ 的极紧容量余量与多层随机对象的条件记账，未经形式化前这两处都是高危区。