Stochastic local search is simpler, and so can be faster, for CSPs that are in the form of propositional satisfiability problems, with Boolean variables and clausal constraints. It can be made more efficient for the following reasons:

• •

  Because only one alternative value exists for each assignment to a variable, the algorithm does not have to search through the alternative values.

• •

  Changing any value in an unsatisfied clause makes the clause satisfied. As a result, it is easy to satisfy a clause, but this may make other clauses unsatisfied.

• •

  If a variable is changed to be true, only those clauses where it appears negatively can become unsatisfied, and all of the clauses where it appears positively must become satisfied. Conversely, if a variable is changed to be false, only those clauses where it appears positively can become unsatisfied, and all of the clauses where it appears negatively must become satisfied. This enables fast indexing of clauses.

• •

  The search space is expanded. In particular, before a solution has been found, more than one of the indicator variables for a variable $Y$ could be true (which corresponds to $Y$ having multiple values) or all of the indicator variables could be false (which corresponds to $Y$ having no values). This can mean that some assignments that were local minima in the original problem may not be local minima in the new representation.

• •

  Satisfiability has been studied much more extensively than most other types of CSPs and more efficient solvers exist because more of the space of potential algorithms has been explored by researchers.

Whether converting a particular CSP to a satisfiability problem makes search performance better is an empirical question.