arXiv cs.AI· Konstantin Kutzkov·· 13 小时前AI 评分18
累积剪枝约束：求解 Max 2-SAT 的精确多项式空间新算法
Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT
AI 导读
研究者提出确定性多项式空间算法，可在 O*(2^(1-γ)n) 时间内精确求解多类子句密度随 n 增长的 Max 2-SAT 实例。该方法扩展经典 DPLL 分支算法，沿分支累积剪枝约束，可剪掉除指数级小比例外的所有赋值。
正文 · AI 翻译
摘要：我们提出了确定性多项式空间算法，可在 $\Ostar(2^{(1-\gamma)n})$ 时间内精确求解 $n$ 个变量上的 Max 2-SAT，其中 $\gamma>0$ 为固定常数，且适用于若干类子句密度可能随 $n$ 增长的实例。我们的主要工具扩展了经典的 DPLL 分支算法。当搜索为某个变量赋予其较不有利的取值时，比较该变量的两个取值会得到一个剪枝约束，而某个最优赋值满足该约束。沿每条分支累积这些约束，可剪除除指数级小部分之外的所有赋值。这些类别包括含许多有偏变量的公式、半随机 2-CNF 公式，以及正则扩展图和由随机块模型生成的图上的 Max-Cut。在半随机公式中，可能共享子句的变量对是任意的，而这些对上的子句是随机的。对于半随机公式和块模型图，算法对每个输入仍然精确，且时间界以高概率在输入上成立。据我们所知，这些是首批针对非平凡类稠密 Max 2-SAT 实例具有如此运行时间的多项式空间算法。除这些类别之外，剪枝约束可以添加到任何 Max 2-SAT 分支算法中，我们预计它们对一般公式具有实际相关性，特别是对稀疏公式，因为每个约束只涉及少数几个变量。
| 评论： | 包含 Lean 验证的项目文件夹：此 https URL |
| 主题： | 数据结构与算法（cs.DS）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.39992 [cs.DS] |
| （或 arXiv:2610.39992v1 [cs.DS] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.39992 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Konstantin Kutzkov [查看电子邮件]
[v1]
2026年10月29日星期四 13:12:14 UTC（87 KB）
来源：arXiv cs.AI · arxiv.org