A Critical View on Local Search Cost: Preliminary Ideas. 

Stochastic Local Search algorithms for satisfiability testing (SAT) have
outperformed complete algorithms on several problem classes, especially on
hard random 3-SAT instances. However, even the most successful algorithms
show a peak in search cost near the `satisfiability threshold'. Several
descriptive cost models have been proposed (backbone size - backbone
fragility). However, it is not clear whether they really explain problem
hardness or just measure 'circumstantial' correlations.

As an alternative, it will be shown that it is the imbalance between the
negated and unnegated occurences of the variables that leads to hard
search spaces. Some simple parameters measuring the effects of imbalance
will be proposed. It will be shown that although they capture the 'reason'
why local search mechanisms are likely to make wrong decisions during the
search, a perfect correlation with search cost is still not to be
expected.

Although the talk concentrates on the WSAT algorithm with random 3-SAT
problems,other problem types will be briefly touched, and the implications
of these findings for local search in general and complete DPLL-like
methods will be discussed.