Jesús Giráldez-Cru, Jordi Levy

Pseudo-Industrial Random SAT Generators


In this paper, we address the problem of random generation of realistic pseudo-industrial SAT instances. First, we review some existing generators which are based on the notions of scale-free structure and community structure. Then, we propose a new generator based on the notion of popularity and similarity. This new model generates instances with both scale-free and community structure, solving the drawbacks of the previous generators.