Backdoors for SAT

Studienarbeiten

• Themenvorschläge für Studien- und Abschlussarbeiten
• Abgeschlossene Arbeiten
  • Algebra und Diskrete Strukturen
  • Automatentheorie
  • Computational Logic
  • Knowledge-aware Artificial Intelligence
  • Logische Programmierung und Argumentation
  • Verifikation und formale quantitative Analyse
  • Wissensbasierte Systeme
• Laufende Studienarbeiten

Toggle side column

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.