提出Max 2-SAT精确多项式空间新算法
热点事件持续更新
提出Max 2-SAT精确多项式空间新算法
1 篇报道1 个报道来源3 小时前更新
先了解这件事
AI 综述
Konstantin Kutzkov在arXiv发布论文，提出基于累积剪枝约束的确定性多项式空间算法，称可在O*(2^((1-γ)n))时间（γ为固定正常数）内精确求解多类稠密Max 2-SAT实例。 该方法扩展经典DPLL分支算法，适用对象包括含大量偏置变量的公式、半随机2-CNF公式，以及正则扩展图和随机块模型图上的Max-Cut问题，且这些实例的子句密度可随n增长。
AI 根据报道生成 · 48 分钟前更新
最新进展10月31日 12:00
累积剪枝约束：Max 2-SAT 精确求解的多项式空间新算法报道时间线
沿着报道，了解事件的不同侧面。
10月31日
- arXiv cs.AI累积剪枝约束：Max 2-SAT 精确求解的多项式空间新算法
论文提出基于累积剪枝约束的确定性多项式空间算法，可在 O*(2^((1-γ)n)) 时间内精确求解多类稠密 Max 2-SAT 实例，其中 γ 为固定正常数。该方法扩展经典 DPLL 分支算法，适用于含大量偏置变量的公式、半随机 2-CNF 公式以及正则扩展图和随机块模型图上的 Max-Cut 问题。
本事件热度走势
还没有足够的连续观测数据，暂不绘制趋势。