English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The local search algorithm WSat is one of the most successful algorithms forsolving the satisfiability (SAT) problem. It is notably effective at solvinghard Random 3-SAT instances near the so-called `satisfiability threshold', butstill shows a peak in search cost near the threshold and large variations incost over different instances. We make a number of significant contributions tothe analysis of WSat on high-cost random instances, using therecently-introduced concept of the backbone of a SAT instance. The backbone isthe set of literals which are entailed by an instance. We find that the numberof solutions predicts the cost well for small-backbone instances but is muchless relevant for the large-backbone instances which appear near the thresholdand dominate in the overconstrained region. We show a very strong correlationbetween search cost and the Hamming distance to the nearest solution early inWSat's search. This pattern leads us to introduce a measure of the backbonefragility of an instance, which indicates how persistent the backbone is asclauses are removed. We propose that high-cost random instances for localsearch are those with very large backbones which are also backbone-fragile. Wesuggest that the decay in cost beyond the satisfiability threshold is due toincreasing backbone robustness (the opposite of backbone fragility). Ourhypothesis makes three correct predictions. First, that the backbone robustnessof an instance is negatively correlated with the local search cost when otherfactors are controlled for. Second, that backbone-minimal instances (which are3-SAT instances altered so as to be more backbone-fragile) are unusually hardfor WSat. Third, that the clauses most often unsatisfied during search arethose whose deletion has the most effect on the backbone. In understanding thepathologies of local search methods, we hope to contribute to the developmentof new and better techniques.

Backbone Fragility and the Local Search Cost Peak