##  [Backdoor Set Size](/backdoor-set-size-0) 

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

 

 

 

 

 

 





## Principle

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

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

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

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

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

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

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

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.