Improving configuration checking for satisfiable random k-SAT instances

摘要: Local search algorithms based on the Configuration Checking (CC) strategy have been shown to be efficient in solving satisfiable random k-SAT instances. The purpose of CC is avoid cycling problem, which corresponds revisiting already flipped variables too soon. It done by considering neighborhood formula variables. In this paper, we propose improve basis an empirical study a powerful algorithm using strategy. first improvement introduces new and simple criterion, refines selection flip for 3-SAT second achieved local Novelty with adaptive noise setting. This enhances efficiency intensification diversification phases when instances k ź 4. We name resulting Ncca+ show its effectiveness treating issued from SAT Challenge 2012. won bronze medal track Competition 2013.