概念
半随机2-CNF公式
SAT理论中的一种公式模型，介于纯随机公式和完全结构化公式之间，子句的底层图结构可以是非随机的，但子句本身随机生成。
时间轴 (近 90 天)
10月30日
论文主要针对三类实例证明了加速效果：含大量偏置变量的公式、半随机2-CNF公式、正则扩展图上的Max-Cut和随机块模型图。
待验证50%
10月30日
对于半随机2-CNF公式，新算法仍然是精确的，并且以高概率在O*(2^{(1-γ)n})时间内完成。
待验证50%
SAT理论中的一种公式模型，介于纯随机公式和完全结构化公式之间，子句的底层图结构可以是非随机的，但子句本身随机生成。
论文主要针对三类实例证明了加速效果：含大量偏置变量的公式、半随机2-CNF公式、正则扩展图上的Max-Cut和随机块模型图。
对于半随机2-CNF公式，新算法仍然是精确的，并且以高概率在O*(2^{(1-γ)n})时间内完成。