Backdoor Set Size
- Natural & Formal Sciences -
Mathematics & Logic Dictionary
Definition
The minimal cardinality of a set of propositional variables such that some assignment to those variables reduces the instance to a member of a specified tractable fragment (e.g., Horn, 2-SAT).