Capturing Structure in SAT and Related Problems
Propositional satisfiability (SAT) and related problems (like Model Counting, QBF-SAT, and CSP) are in practise often much easier to solve than suggested by their respective theoretical worst-case complexities. This friendliness of the real world is often explained by the presence of some kind of a hidden structure in practical problem instances. In this talk we will review some mathematical concepts, in particular from the area of parameterized complexity, that attempt to capture the structure in problem instances and discuss their virtues and limits. We will focus rather on general questions than on technical details.