Thema3439: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Sibylle Möhle (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Serge Stratan (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
Zeile 8: | Zeile 8: | ||
|Forschungsgruppe=Wissensverarbeitung | |Forschungsgruppe=Wissensverarbeitung | ||
|Abschlussarbeitsstatus=Abgeschlossen | |Abschlussarbeitsstatus=Abgeschlossen | ||
|Abgabe=2011 | |Beginn=2011/10/01 | ||
|Abgabe=2011/10/01 | |||
|Ergebnisse=Gario thesis.pdf | |Ergebnisse=Gario thesis.pdf | ||
|Beschreibung DE=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. | |||
|Beschreibung EN=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. | |||
}} | }} |
Aktuelle Version vom 29. November 2016, 22:25 Uhr
Backdoors for SAT
Masterarbeit von Marco Gario
- Betreuer Steffen Hölldobler
- Wissensverarbeitung
- 01. Oktober 2011 – 01. Oktober 2011
- Download
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).
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.