Abstract
Clause-elimination techniques that simplify formulas by removing redundant clauses play an important role in modern SAT solving. Among the types
of redundant clauses, blocked clauses are particularly popular. For checking whether a clause C is
blocked in a formula F, one only needs to consider the so-called resolution neighborhood of C,
i.e., the set of clauses that can be resolved with C.
Because of this, blocked clauses are referred to as
being locally redundant. In this paper, we discuss
powerful generalizations of blocked clauses that are
still locally redundant, namely set-blocked clauses
and super-blocked clauses. We furthermore present
complexity results for deciding whether a clause is
set-blocked or super-blocked