Kilby, Philip; Slaney, John K; Thiebaux, Sylvie; Walsh, Toby
We study the backbone and the backdoors of prepositional satisfiability problems. We make a number of theoretical, algorithmic and experimental contributions. From a theoretical perspective, we prove that backbones are hard even to approximate. From an algorithmic perspective, we present a number of different procedures for computing backdoors. From an empirical perspective, we study the correlation between being in the backbone and in a backdoor. Experiments show that there tends to be very...[Show more]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.