Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Thema3439
Abgabe 1 Oktober 2011  +
Abschlussarbeitsstatus Abgeschlossen  +
Abschlussarbeitstyp Master  +
Beginn 1 Oktober 2011  +
Beschreibung DE The concept of backdoor was introduced to
The concept of backdoor was introduced to try to explain the good performances achieved on real world SAT instances by solvers. A backdoor is a set of variables that, once decided, makes the rest of the problem simple (i.e. polynomial-time).<br/> In this thesis we provide a comprehensive overview on the state of the art of backdoors for SAT. Moreover, we study the relation between backdoors and parameterized complexity. In order to do so, we consider the problem of finding a smallest strong Hornbackdoor and we study it by means of the parameterized version of Vertex Cover. We conclude by presenting some interesting results obtained when analysing strong Hornbackdoors in instances from different domains.
doors in instances from different domains.  +
Beschreibung EN The concept of backdoor was introduced to
The concept of backdoor was introduced to try to explain the good performances achieved on real world SAT instances by solvers. A backdoor is a set of variables that, once decided, makes the rest of the problem simple (i.e. polynomial-time).<br/> In this thesis we provide a comprehensive overview on the state of the art of backdoors for SAT. Moreover, we study the relation between backdoors and parameterized complexity. In order to do so, we consider the problem of finding a smallest strong Hornbackdoor and we study it by means of the parameterized version of Vertex Cover. We conclude by presenting some interesting results obtained when analysing strong Hornbackdoors in instances from different domains.
doors in instances from different domains.  +
Betreuer Steffen Hölldobler +
Download Gario thesis.pdf  +
Forschungsgruppe Wissensverarbeitung +
Nachname Gario  +
Student Marco Gario  +
Titel DE Backdoors for SAT  +
Titel EN Backdoors for SAT  +
Vorname Marco  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
Thema3439 + , Thema3439 +
Kategorien Abschlussarbeit
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
29 November 2016 20:25:23  +
verstecke Attribute die hierhin verlinken 
  Keine Attribute verlinken auf diese Seite.
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.