SAT distributions with planted assignments and phase transitions between decision and optimization problems Original Research Article

We present a generator for weighted instances of MAX image-SAT in which every clause has a weight associated with it and the goal is to maximize the total weight of satisfied clauses. Our generator produces formulas whose hardness can be finely tuned by two parameters image and image that control the weights of the clauses. Under the right choice of these parameters an easy–hard–easy pattern in the search complexity emerges which is similar to the patterns observed for traditional SAT distributions.