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

Furthermore, we demonstrate that these phase transitions are related to sudden changes to a quantity similar to the backbone of a SAT formula. In our model not only we know how the optimal solution looks like (because we plant it in advance) but we also give evidence that it is unique. Thus our generator comes with an indication of optimality of the planted assignment which is basically the structural property that is related to the phase transition phenomena observed.