La cardinalité minimale d'un ensemble de variables propositionnelles telles que certaines assignations de ces variables réduisent l'instance à un fragment tractable spécifié (par exemple Horn, 2-SAT).

Principe

Identifier de petits ensembles de variables contrôlables dont la fixation effondre la difficulté globale en un sous-problème tractable ; la taille est mesurée par rapport à une classe cible choisie.

Démonstration

Pour la CNF { (¬a ∨ b), (¬b ∨ c), (a ∨ b ∨ c) }, fixer a = faux et b = vrai peut réduire la formule résiduelle en une instance Horn ; si deux variables suffisent, la Taille De L'Ensemble Backdoor ≤ 2.

Mauvaise application

Annoncer une taille de backdoor sans préciser la classe tractable cible ou en autorisant des réductions oraculaires arbitraires dénature la notion et peut produire des nombres artificiellement petits.

Conséquence

Une petite Taille De L'Ensemble Backdoor permet des algorithmes à paramètre fixe : explorer exponentiellement seulement en la taille du backdoor tout en résolvant l'instance résiduelle tractable en temps polynomial.

Inversion

Si aucun petit backdoor n'existe pour une classe cible raisonnable, l'instance résiste à cette paramétrisation, indiquant une difficulté structurelle intrinsèque même si le nombre de clauses est modéré.

Limite

Dépend du choix du fragment tractable cible et du modèle de réduction (assignations partielles versus transformations préservant la structure) ; la notion n'est pas intrinsèque tant que la cible n'est pas fixée.

Tension sémantique

Tension avec la Densité De Clauses et le Nombre De Littéraux : des instances denses peuvent avoir de petits backdoors, et des instances clairsemées peuvent en manquer, de sorte que la taille du backdoor capture un axe différent de facilité structurelle.

Synthèse

La Taille De L'Ensemble Backdoor quantifie le plus petit ensemble de variables de contrôle dont l'assignation transforme un problème en une classe tractable choisie ; c'est un paramètre qui explique pourquoi certaines instances syntaxiquement complexes sont algorithmiquement faciles.