58 citations · 327 across the 60 of their papers we have counts for
Showing 2013 · cs.CCShow all
3 papers · 2 filters
cs.CC2013★ 6 cited
The Parameterized Complexity of Reasoning Problems Beyond NP
Ronald de Haan, Stefan Szeider
Today's propositional satisfiability (SAT) solvers are extremely powerful and can be used as an efficient back-end for solving NP-complete problems. However, many fundamental probl…
cs.CC2013★ 6 cited
On the Subexponential Time Complexity of CSP
Iyad Kanj, Stefan Szeider
A CSP with n variables ranging over a domain of d values can be solved by brute-force in d^n steps (omitting a polynomial factor). With a more careful approach, this trivial upper…
cs.CC2013★ 4 cited
Local Backbones
Ronald de Haan, Iyad Kanj, Stefan Szeider
A backbone of a propositional CNF formula is a variable whose truth value is the same in every truth assignment that satisfies the formula. The notion of backbones for CNF formulas…