##  [Backdoor-Setgröße](/de/node/60896) 

 Definition

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

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

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

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

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

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

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

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

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.