Backbones and backdoors in satisfiability
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]
|Collections||ANU Research Publications|
|Source:||Proceedings of The Twentieth National Conference on Artificial Intelligence and The Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI-2005 / IAAI-2005)|
|01_Kilby_Backbones_and_backdoors_in_2005.pdf||155.18 kB||Adobe PDF||Request a copy|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.