Den lokala sökalgoritmen WSat är en av de mest framgångsrika algoritmerna för att lösa problemet med satis (SAT). Den är särskilt effektiv på att lösa svåra Random 3-SAT fall nära den s.k. "satis kapacitetströskeln", men visar fortfarande en topp i sökkostnader nära tröskeln och stora variationer i kostnader över olika fall. Vi gör ett antal betydande bidrag till analysen av WSat på högkostnads slumpmässiga fall, med hjälp av det nyligen införda konceptet av ryggraden i en SAT instans. Ryggraden är den uppsättning ordagranna ordagranner som är förknippade med ett exempel. Vi skulle vilja att antalet lösningar förutspår kostnaden väl för småryggiga fall men är mycket mindre relevant för de stora ryggbenen som verkar nära tröskeln och dominerar i den överkonsekventa regionen. Vi visar ett mycket starkt samband mellan sökkostnaden och hammingavståndet till närmaste lösning tidigt i WSats sökning. Detta mönster får oss att införa ett mått på ett exempels ryggradssårbarhet, vilket visar hur ihållande ryggraden är när klausuler tas bort. Vi föreslår att billiga slumpmässiga fall för lokal sökning är de med mycket stora ryggradar som också är ryggradsfragila. Vi föreslår att sönderfallet i kostnad utöver satis kapacitetströskeln beror på ökad ryggrad robusthet (motsatsen till ryggraden bräcklighet). Vår hypotes gör tre korrekta förutsägelser. För det första, att ryggraden robusthet en instans är negativt korrelerad med den lokala sökkostnaden när andra faktorer kontrolleras för. För det andra, att ryggrad-minimal fall (som är 3-SAT fall ändras så att vara mer ryggrad-fragil) är ovanligt svårt för WSat. För det tredje, att de klausuler som oftast är otillfredsställda under sökandet är de vars radering har mest eekt på ryggraden. För att förstå de lokala sökmetodernas patologier hoppas vi kunna bidra till utvecklingen av nya och bättre tekniker.
Problem med en liten ryggrad verkar ha ett starkare samband mellan antalet lösningar och en lokal söksvårigheter REF.
Backbone Fragility and the Local Search Cost Peak
{'venue': 'Journal Of Artificial Intelligence Research, Volume 12, pages 235-270, 2000', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}