结果族 118：Bin packing and unbounded configuration-LP gaps · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
搬家装箱：一堆物品、容量 1 的箱子、目标最省箱。业内长期相信一个温和的猜想：”理想规划（允许把物品磨成粉分装）算出的箱数，顶多比真实答案多 1 箱”。这篇论文把它推翻：差距可以任意大；而且除非 P=NP，任何算法都保证不了”只多固定几个箱子”。
关键词卡片
@@M@@\mathrm{OPT}\le\lceil\mathrm{LP}\rceil+1@@，本文否定。看个具体例子
数字版定理：对任意 @@M@@c\ge0@@，存在每件物品 @@M@@>\tfrac16@@ 的实例，使 @@M@@\mathrm{LP}=B@@ 恰为整数、而 @@M@@\mathrm{OPT}>B+c@@。取 @@M@@c=1@@：规划说 @@M@@B@@ 箱够，现实却至少要 @@M@@B+2@@ 箱——直接超出猜想允许的余量。定理 2 进一步说：区分”@@M@@B@@ 箱够”与”@@M@@B+c@@ 箱不够”是 NP-难的。
直觉上，规划允许”半个物品进这箱、半个进那箱”，现实物品却不能切开。论文的归约把图的顶点覆盖难题悄悄编码进物品尺寸的小数位，再靠”两棵竞争树”的组合障碍，让分数世界与整数世界分道扬镳到任意远。
为什么值得关心
一个悬置三十年的猜想被干净利落地否定，同时 Williamson–Shmoys 教科书里”是否存在加性近似算法”的公开问题得到否定答案。
已 Lean 形式化
第一级台阶
入门导读用搬家装箱作比：业内长期相信”理想规划（允许把物品磨成粉分装）算出的箱数，顶多比真实答案多一箱”。翻译一下：对象是一份带尺寸的物品清单和容量为一的箱子；操作是把物品整件分进箱子；”磨粉”对应允许物品按分数分摊的规划版本。论文的两记重拳是：粉装与整装的箱数差可以超过任何事先给定的数；而且除非 P=NP，任何快速算法都保证不了”只多固定几个箱子”。
第二级台阶
用本科术语说：装箱问题求最小箱数 @@M@@\OPT(I)@@；配置线性规划给可行装箱模式（总尺寸 @@M@@\le1@@ 的物品子集）赋非负分数权并覆盖每件物品的需求，其值 @@M@@\LP(I)\le\OPT(I)@@。修正整数取整猜想（MIRUP）断言 @@M@@\OPT\le\lceil\LP\rceil+1@@。加性近似问是否存在多项式算法与绝对常数 @@M@@C@@ 使输出不超过 @@M@@\OPT+C@@ 箱。归约的源头是图论里的顶点覆盖：取到每条边至少一个端点的最小顶点集。
第三级台阶
定理 1（thm:unbounded-gap）在此陈述：对任意整数 @@M@@c\ge0@@，存在每件尺寸 @@M@@>\tfrac16@@（故每箱至多 5 件）的有理实例与整数 @@M@@B@@，使 @@M@@\LP(I)=B@@ 恰为整数而 @@M@@\OPT(I)>B+c@@，且对按尺寸类型与按物品副本两种配置松弛同时成立——这是无条件的结构性反例，取 @@M@@c=1@@ 即推翻 MIRUP。定理 2 把同一”图到装箱”归约接到 Håstad 间隙上：区分”@@M@@B@@ 箱够”与”@@M@@B+c@@ 箱不够”是 NP-难的；推论给出：常数加性近似算法存在当且仅当 @@M@@\classP=\classNP@@。归约接口是：大小 @@M@@\le k@@ 的覆盖导出 @@M@@B@@ 箱装法，而 @@M@@B+c@@ 箱内的任何装法都导出 @@M@@\le k+\rho n@@ 的覆盖。
论文证明：装箱问题的配置线性规划（configuration LP）值与真实最优箱数之间可以存在任意大的加性间隙，直接推翻 Scheithauer–Terno 的修正整数取整猜想（@@M@@\OPT\le\lceil\LP\rceil+1@@）；并且除非 @@M@@\classP=\classNP@@，任何多项式算法都无法保证只多用固定常数个箱子。两个结论都已在”每件物品大于 @@M@@1/6@@“的约束下成立。
装箱问题（bin packing）给定一份有理数尺寸的物品清单，箱容量为 @@M@@1@@，目标是求最小箱数 @@M@@\OPT(I)@@。它最重要的下界来自 Gilmore–Gomory 的配置线性规划（configuration LP），实践中 LP 值几乎就是整数最优。Marcotte 在 1985 年给出取整性质失效的切割下料实例后，Scheithauer 与 Terno 于 1995/1997 年提出修正整数取整猜想（Modified Integer Round-Up Conjecture，MIRUP）：@@M@@\OPT(I)\le\lceil\LP(I)\rceil+1@@，三十年来悬而未决。算法方面，Williamson 与 Shmoys 在 2011 年的近似算法教科书中把”是否存在多项式时间算法与绝对常数 @@M@@C@@ 保证 @@M@@\OPT(I)+C@@ 个箱子”列为公开问题。已知最好上界是 Hoberg–Rothvoss 的 @@M@@O(\log\OPT)@@ 加性界；下界方面此前只有零星的不满足取整性质的例子与针对特定舍入方式的对数障碍，无界加性间隙始终无人建立。
定理 1（无界配置间隙）：对任意整数 @@M@@c\ge0@@，存在有限的有理数物品实例 @@M@@I@@ 与整数 @@M@@B@@，使每件物品尺寸大于 @@M@@1/6@@（于是每箱至多装 5 件），且
@@M@@D\LP(I)=B,\qquad \OPT(I)>B+c.@@
该等式对两种配置松弛同时成立：按数值尺寸类型的经典 Gilmore–Gomory 形式，以及模式限制为具体物品副本子集的更强形式。取 @@M@@c=1@@ 即与 MIRUP 矛盾——且因 @@M@@\LP@@ 恰为整数 @@M@@B@@，间隙超出猜想允许的余量，不涉及任何取整歧义。
定理 2（固定加性硬度）：对每个固定的 @@M@@c\ge0@@，区分”@@M@@I@@ 能装进 @@M@@B@@ 个箱子”与”@@M@@I@@ 装不进 @@M@@B+c@@ 个箱子”是 NP-难的，物品尺寸为有理数且都大于 @@M@@1/6@@。
推论：存在确定性多项式时间算法总用至多 @@M@@\OPT(I)+C@@ 个箱子，当且仅当 @@M@@\classP=\classNP@@。论文并说明对数级上界与定理 1 不矛盾：实例规模随预设间隙增长极快，论文未得到关于实例规模的匹配下界。
全文核心是一座统一的”图到装箱”归约（graph-to-packing reduction）：输入显式图 @@M@@G@@（@@M@@n@@ 个顶点）与覆盖目标 @@M@@k@@，多项式时间输出整数 @@M@@B@@ 与 @@M@@5B@@ 个有理尺寸物品，满足两条——若 @@M@@G@@ 有大小至多 @@M@@k@@ 的顶点覆盖（vertex cover），物品可装入 @@M@@B@@ 箱；反之，任何装入至多 @@M@@B+c@@ 箱的方案都导出大小至多 @@M@@k+\rho n@@ 的顶点覆盖。
先造”两棵竞争树”（competing trees）。对参数 @@M@@d@@ 构造辅助树 @@M@@\mathcal T@@：分 @@M@@2d-1@@ 个相位，每相位在当前叶 @@M@@u_i@@ 下挂 @@M@@M_i=2^i@@ 条脊线（spine），而该深度的标记配额只给 @@M@@p=2^{i-1}=M_i/2@@ 个，鸽笼原理保证总有一条脊线完全未被标记；脊线端点的延伸链数目也比剩余标记预算恰好多一，于是避让可以一路推进到叶。脊线端点一半染红一半染蓝，每条根到叶路径恰好遇到 @@M@@2d-1@@ 个有色顶点，故至少 @@M@@d@@ 个同色。按”红 @@M@@\ge d@@“与”蓝 @@M@@\ge d@@“分别剪枝得到 @@M@@T^+,T^-@@：各自都能在配额内把每条路径打中 @@M@@d@@ 次；但把两树的标记投影回 @@M@@\mathcal T@@ 合并后仍是合法的配额标记，必然漏掉一条路径——共享配额时两树不可能同时全覆盖。这个纯粹的组合障碍是全篇的引擎。
再把图编码成物品。每个顶点标签拥有两棵树的嵌套区间胞（nested interval cells）副本，图中边的每个重复位置对应一个作业胞（job cell）。物品分五种角色：行（row）、锚（anchor）、全局与局部辅助（global/local auxiliary）、旗（flag），实际尺寸取
@@M@@Da_i=\tfrac15+\gamma p(i)+\mu q(i)+\nu w(i).@@
主分数 @@M@@p(i)@@ 以 @@M@@100@@ 为基把十条齐次计数方程压缩进一个整数，强制可行的满箱基本只能取四种”表模式”；次分数 @@M@@q(i)=\pm 3^v@@ 强制三种带标签角色共享同一标签（好元组）；最小的微扰 @@M@@\nu w(i)@@ 让好元组的可行性恰好等价于坐标不等式 @@M@@h\le z@@（@@M@@\mathrm M@@ 型箱的”完成不超过截止”）或 @@M@@\mathrm G@@ 型箱的关键不等式，其差恰记录半开覆盖区间 @@M@@[h,b)@@。守恒论证——全库存主分数为零、满箱主分数非正——保证至多 @@M@@K@@ 个物品逃出表模式、每个顶点至多 @@M@@3K@@ 个锚逃出好元组，且该误差与顶点的位置数无关，这正是能抗住 @@M@@c@@ 个额外箱子的关键。
完备性方向：取大小恰为 @@M@@k@@ 的覆盖 @@M@@C@@，被选中顶点用长度 @@M@@1@@ 的全局物品给 plus 侧注资，其 @@M@@d@@ 个注资根行把整侧覆盖 @@M@@d@@ 次；未选中侧改用该侧树的 @@M@@d@@ 重标记做局部物品覆盖每个叶测试；前缀计数再把截止（deadline）与完成坐标排序配对。可靠性方向：若真能装进 @@M@@B+c@@ 箱，前缀分解迫使每个测试点被覆盖至少 @@M@@d-6K@@ 次；若某顶点两侧注资都不足，覆盖区间导出的标记恰好满足合并配额却打中两树所有路径，与竞争树引理矛盾，故每个顶点某一侧注资 @@M@@\ge d-6K@@；边的通行证（permit）资源守恒再迫使每条边至少有一个端点 plus 注资超过 @@M@@d/8@@，这些端点构成大小 @@M@@\le k+\rho n@@ 的覆盖。
最后两条定理分道扬镳。结构间隙取四顶点团、@@M@@k=2@@、@@M@@\rho=1/8@@：最小覆盖为 @@M@@3>2+n/8=5/2@@，故装不进 @@M@@B+c@@ 箱；同时每个顶点”选中/未选中”两个局部状态各赋权 @@M@@1/2@@ 的显式分数混合给出值为 @@M@@B@@ 的可行分数解，而每件物品大于 @@M@@1/6@@ 给出对偶下界 @@M@@B@@，于是 @@M@@\LP=B@@——这一步不依赖任何复杂性假设。硬度定理则把图换成 Håstad 3-SAT 间隙（@@M@@\eta=1/16@@）导出的子句图（@@M@@n=3M@@，@@M@@k=2M@@，取 @@M@@\rho=1/96<\eta/3@@），即得 NP-硬度；推论的另一方向在 @@M@@\classP=\classNP@@ 下用二分搜索直接构造最优装箱。
主结果已由 Lean 形式化证明（见结果族 118 的 Lean 文档）。论文两条主线互相支撑：定理 1 是无条件的，只用到四顶点团、分数见证与可靠性引理，完全不依赖 PCP；定理 2 复用同一归约构造，仅把输入图换成带间隙的子句图。按 OpenAI 官方声明，未经形式化的结果可能有问题，而本篇恰属已形式化之列，可信度较高。
问 1：整个构造的引擎是什么，它为什么对？
答：竞争树引理（lem:competing-trees）：两棵带深度配额的有限根树，各自单独都存在把每条根到叶路径打中 @@M@@d@@ 次的合规标记；但共享同一份配额时，两树不可能连”每条路径至少中一次”都同时做到。证明靠纯鸽笼：每相位的标记配额只有该深度脊线数的一半，总有脊线完全未标记，避让可一路推到叶。这个组合障碍与复杂度无关，是全篇的分岔点。
问 2：定理 1 是无条件的，定理 2 却是 NP-硬度——为何要分两条腿走路？
答：引言明言：MIRUP 关心装法的存在性，近似算法问题关心高效构造，二者需要不同论证。定理 1 用四顶点团、@@M@@k=2@@ 与”每个局部状态赋权 @@M@@1/2@@“的显式分数见证给出 @@M@@\LP=B@@，可靠性引理排除 @@M@@B+c@@ 箱整装，全程不碰复杂度类；定理 2 把同一归约接到 Håstad 3-SAT 间隙导出的子句图上，才引入 NP-硬度。共享的是归约骨架，不是假设。
问 3：为什么每件物品大于 @@M@@1/6@@ 的限制值得强调？
答：它把每箱物品数压到至多 5，说明反例与硬度在最受限的装箱形态下仍成立；同时它划清了与”固定尺寸种类数则多项式可解”（Goemans–Rothvoss）的界限——本文实例的尺寸种类数仍可增长，只是单箱基数有界。
问 4：与此前工作相比真正的新意是什么？
答：MIRUP 悬置约三十年；此前 Marcotte 只给出取整性质失效的个例，Caprara 等的边着色编码造不出无界间隙，差异构障碍也只针对”舍入给定分数支撑”的算法。对完整配置 LP 的间隙必须控制一切可行整装而非仅给定支撑——这正是本文提取论证（主分数守恒把逃逸物品压到有界个数，且误差与顶点位置数无关）新解决的任务。
问 5：@@M@@O(\log\OPT)@@ 的加性上界为何不与定理 1 矛盾？
答：论文明言：构造实例的规模随预设间隙增长极快，定理只保证间隙存在，并不给出关于实例规模的对数级匹配下界。Hoberg–Rothvoss 的 @@M@@O(\log\OPT)@@ 上界与”间隙可以任意大”在规模轴上完全相容；真正的定量空隙论文未填。
问 6：这种巨型归约最可能在哪里出错？AI 风险如何？
答：高危点是五角色物品的数值编码（基 100 主分数、@@M@@\pm3^v@@ 次分数、微扰）与”任意可行装法”的提取论证——满箱模式分类或守恒不等式错一处，可靠性即漏。据结果族元信息，主结果已附 Lean 形式化证明，这类风险已大幅对冲；残余风险在与外部结果的定量比对陈述。
问 7：谁会用到它？
答：装箱与切割下料社区：MIRUP 被干净否定，Williamson–Shmoys 教科书的常数加性公开问题得到否定答案；今后加性近似的正确目标是 @@M@@\OPT+\mathrm{polylog}@@ 级，配置 LP 的使用者也须正视其无界加性间隙。
总评
一个三十年猜想加一个教科书开放问题被同一归约双杀，且主结果经 Lean 形式化，是高置信度的硬结果；剩余悬念是间隙作为实例规模函数的定量下界——那决定 @@M@@O(\log\OPT)@@ 型上界是否已经最优。