新算法在多项式空间内精确求解多类稠密 Max 2-SAT
论文AI 评分 58/100arXiv cs.AI待复核
AI 聚合
本条为 AI 依据下方公开信源自动整理生成的摘要，不构成转载，可能存在偏差，请以原文为准。整理者：贝果科技 AI 资讯助手。
一篇 arXiv 论文提出确定性多项式空间算法，可在若干类子句密度随变量数增长的实例上，以 O*(2^{(1-γ)n}) 的时间精确求解 Max 2-SAT。方法扩展经典 DPLL 分支：当变量取较差值时，比较该变量的两个取值可得到一条被某个最优解满足的剪枝约束，沿分支累积这些约束可剪掉除指数级小比例外的所有赋值。覆盖的实例类包括含大量偏置变量的公式、半随机 2-CNF 公式，以及正则扩展图与随机块模型图上的 Max-Cut。对半随机公式和块模型图，算法对每个输入仍精确，时间界以高概率成立。作者称这是首个对非平凡稠密 Max 2-SAT 实例类具有该运行时间的多项式空间算法，并提供了 Lean 验证项目。
全文梳理
AI 摘要依据下方信源原文自动整理，非原文转载算法做了什么
论文针对 Max 2-SAT 给出确定性多项式空间算法，在若干类实例上以 O*(2^{(1-γ)n}) 的时间精确求解，其中 n 为变量数，γ 为固定正数。这些实例的共同点是子句密度可以随 n 增长，而非固定稀疏。作者强调，在此之前，对非平凡稠密 Max 2-SAT 实例类，尚无多项式空间算法能达到这样的运行时间。算法不依赖随机化，空间保持多项式级别。
剪枝约束怎么来
方法建立在经典 DPLL 分支算法之上。搜索过程中，当某个变量被赋予较差的那个取值时，把该变量的两个取值作比较，可以得到一条剪枝约束，而这条约束会被某个最优赋值满足。沿每条分支把这些约束累积起来，就能排除掉除指数级小比例之外的全部赋值，从而压缩搜索空间。这一机制是算法取得时间界的关键，作者将其视为对 DPLL 框架的扩展。
适用范围与验证
算法覆盖三类实例：含大量偏置变量的公式、半随机 2-CNF 公式，以及正则扩展图与随机块模型图上的 Max-Cut。在半随机公式中，可能共享子句的变量对是任意的，而这些对上的子句是随机的；对半随机公式和块模型图，算法对每个输入都保持精确，时间界以高概率成立。作者还指出，剪枝约束可以加入任何 Max 2-SAT 分支算法，并预计在稀疏公式上有实用价值，因为此时每条约束只涉及少数变量。论文附带 Lean 验证项目。
为什么值得看
精确求解 Max 2-SAT 的新剪枝思路，附 Lean 形式化验证，对算法与组合优化研究者有参考价值。
论文
信源1 家
关键事实
相关 · 论文
本页内容由 AI 自动聚合公开信源生成，仅供了解行业动态参考，不构成任何投资或决策建议。如需引用请以原文出处为准。