Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively

Haixia Jia, Cristopher Moore, Doug Strain

To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is…