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).

Principle

Identify small controllable variable sets whose fixing collapses global hardness into a tractable subproblem; the size is measured with respect to a chosen target class.

Demonstration

Given CNF { (¬a ∨ b), (¬b ∨ c), (a ∨ b ∨ c) }, assigning a = false and b = true might reduce the residual formula to a Horn instance; if two variables suffice, Backdoor Set Size ≤ 2.

Misapplication

Reporting a backdoor size without specifying the target tractable class or allowing arbitrary oracle reductions misrepresents the notion and can produce meaningless small numbers.

Consequence

A small Backdoor Set Size yields fixed-parameter algorithms: explore exponentially only in the backdoor size while solving the residual tractable instance in polynomial time.

Reversal

If no small backdoor exists for any reasonable target class, the instance resists parameterization by this measure, indicating inherent structural hardness even if clause counts are modest.

Boundary

Depends on the choice of target tractable fragment and the model of reduction (partial assignments versus structure-preserving transformations); not intrinsic unless the target is fixed.

Semantic Tension

Tension with Clause Density and Literal Count: dense instances can still have tiny backdoors, and sparse instances can lack small backdoors, so backdoor size captures a different axis of structural easiness.

Synthesis

Backdoor Set Size quantifies the smallest control set of variables whose assignment transforms a problem into a chosen tractable class; it is a parameter that explains why some syntactically complex instances are algorithmically easy.