Stochastic local search (SLS) is a successful paradigm for solving the satisfiability problem of propositional logic. A recent development in this area involves solving not the original instance, but a modified, yet logically equivalent one. Empirically, this technique was found to be promising as it improves the performance of state-of-the-art SLS solvers. Currently, there is only a shallow understanding of how this modification technique affects the runtimes of SLS solvers. Thus, we model this modification process and conduct an empirical analysis of the hardness of logically equivalent formulas. Our results are twofold. First, if the modification process is treated as a random process, a lognormal distribution perfectly characterizes the hardness; implying that the hardness is long-tailed. This means that the modification technique can be further improved by implementing an additional restart mechanism. Thus, as a second contribution, we theoretically prove that all algorithms exhibiting this long-tail property can be further improved by restarts. Consequently, all SAT solvers employing this modification technique can be enhanced.
翻译:本地斯托切搜索( SLS) 是解决命题逻辑的可比较性问题的成功范例。 该领域最近的一项发展涉及的不是解决原始实例, 而是解决一个经过修改的、但逻辑上对等的原始实例。 生动地, 这一技术被认为很有希望, 因为它能改善最先进的 SLS 解答器的性能。 目前, 对这一修改技术如何影响 SLS 解答器的运行时间只有浅薄的理解。 因此, 我们模拟了这一修改过程, 并对逻辑上等同的公式的硬性进行了实验性分析。 我们的结果是双重的。 首先, 如果将修改过程作为随机过程处理, 逻辑上正常的分布可以完全描述硬性; 意味着硬性是长的。 这意味着通过实施额外的重新启动机制可以进一步改进修改技术。 因此, 作为第二个贡献, 我们理论上证明, 显示这种长尾的属性的所有算法可以通过重新启动来进一步改进。 因此, 使用这种修改技术的所有 SAT 解答器都可以得到加强 。