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

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

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

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

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

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

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

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.