Die minimale Kardinalität einer Menge von propositionalen Variablen, sodass durch eine Belegung dieser Variablen die Instanz in eine festgelegte lösbare Teilklasse (z. B. Horn, 2-SAT) überführt wird.

Prinzip

Kleine steuerbare Variablenmengen identifizieren, deren Fixierung globale Härte in ein lösbares Teilproblem überführt; die Größe bezieht sich auf eine gewählte Zielklasse.

Demonstration

Für die CNF { (¬a ∨ b), (¬b ∨ c), (a ∨ b ∨ c) } kann durch Setzen a = false und b = true die Restformel zu einer Horn-Instanz werden; wenn zwei Variablen ausreichen, ist die Backdoor-Setgröße ≤ 2.

Fehlanwendung

Die Angabe einer Backdoor-Setgröße ohne Festlegung der Zielklasse oder unter Zulassung beliebiger Orakelreduktionen verfälscht den Begriff und kann bedeutungslose kleine Werte liefern.

Konsequenz

Eine kleine Backdoor-Setgröße ermöglicht Fixed-Parameter-Algorithmen: exponentielles Durchsuchen nur in der Backdoor-Größe, während die verbleibende lösbare Instanz in Polynomialzeit gelöst wird.

Umkehrung

Existiert für keine sinnvolle Zielklasse ein kleiner Backdoor, so widersteht die Instanz dieser Parametrisierung und weist auf inhärente strukturelle Härte hin, selbst wenn die Klauselanzahl moderat ist.

Abgrenzung

Hängt von der Wahl der zielhaften lösbaren Teilklasse und dem Reduktionsmodell (partielle Belegungen versus struktur-erhaltende Transformationen) ab; nicht intrinsisch, solange das Ziel nicht fixiert ist.

Semantische Spannung

Spannung mit Klauseldichte und Anzahl Der Literale: Dichte Instanzen können kleine Backdoors besitzen und dünne Instanzen können keine haben, sodass die Backdoor-Größe eine andere Achse struktureller Leichtigkeit erfasst.

Synthese

Die Backdoor-Setgröße quantifiziert die kleinste Steuerungsmenge von Variablen, deren Belegung ein Problem in eine gewählte lösbare Klasse überführt; sie ist ein Parameter, der erklärt, warum manche syntaktisch komplexen Instanzen algorithmisch einfach sind.