##  [Tamaño del Conjunto Backdoor](/es/node/60896) 

 Definición

La cardinalidad mínima de un conjunto de variables proposicionales tal que alguna asignación de esas variables reduce la instancia a un fragmento tratable especificado (p. ej., Horn, 2-SAT).

 

 

 

 

 

 





## Principio

Principio

Identificar pequeños conjuntos de variables controlables cuya fijación colapsa la dureza global a un subproblema tratable; el tamaño se mide respecto a una clase objetivo elegida.

 

 

 

 

 





## Demostración

Demostración

Dada la CNF { (¬a ∨ b), (¬b ∨ c), (a ∨ b ∨ c) }, asignar a = falso y b = verdadero puede reducir la fórmula residual a una instancia Horn; si dos variables bastan, el Tamaño Del Conjunto Backdoor ≤ 2.

 

 

 

 

## Aplicación incorrecta

Aplicación incorrecta

Reportar un tamaño de backdoor sin especificar la clase tratable objetivo o permitiendo reducciones arbitrarias mediante oráculo tergiversa la noción y puede producir números artificialmente pequeños.

 

 

 

 

 





## Consecuencia

Consecuencia

Un tamaño de backdoor pequeño permite algoritmos parametrizados: explorar exponencialmente solo en el tamaño del backdoor mientras se resuelve la instancia residual tratable en tiempo polinómico.

 

 

 

 

## Inversión

Inversión

Si no existe un backdoor pequeño para ninguna clase objetivo razonable, la instancia resiste esta parametrización, indicando dureza estructural inherente incluso con recuentos de cláusulas modestos.

 

 

 

 

 





## Límite

Límite

Depende de la elección del fragmento tratable objetivo y del modelo de reducción (asignaciones parciales frente a transformaciones que preservan la estructura); no es intrínseco a menos que la objetivo esté fijado.

 

 

 

 

 





## Tensión semántica

Tensión semántica

Tensión con la Densidad De Cláusulas y el Conteo De Literales: instancias densas pueden tener backdoors pequeños y las dispersas pueden carecer de ellos, por lo que el tamaño de backdoor captura un eje distinto de facilidad estructural.

 

 

 

 

 





## Síntesis

Síntesis

El Tamaño Del Conjunto Backdoor cuantifica el conjunto mínimo de variables de control cuya asignación transforma un problema en una clase tratable elegida; es un parámetro que explica por qué algunas instancias sintácticamente complejas son algorítmicamente fáciles.