Outputs (2)

Backdoor Sets for DLL Subsolvers (2005)
Journal Article
Szeider, S. (2005). Backdoor Sets for DLL Subsolvers. Journal of Automated Reasoning, 35(1-3), 73-88. https://doi.org/10.1007/s10817-005-9007-9

We study the parameterized complexity of detecting small backdoor sets for instances of the propositional satisfiability problem (SAT). The notion of backdoor sets has been recently introduced by Williams, Gomes, and Selman for explaining the ‘heavy-... Read More about Backdoor Sets for DLL Subsolvers.

The Complexity of Resolution with Generalized Symmetry Rules (2005)
Journal Article
Szeider, S. (2005). The Complexity of Resolution with Generalized Symmetry Rules. Theory of Computing Systems, 38(2), 171-188. https://doi.org/10.1007/s00224-004-1192-0

We generalize Krishnamurthys well-studied symmetry rule for resolution systems by considering homomorphisms instead of symmetries; symmetries are injective maps of literals whichpreserve complements and clauses; homomorphisms arise from symmetries by... Read More about The Complexity of Resolution with Generalized Symmetry Rules.