Capturing Structure in SAT and Related Problems
Speaker:
Stefan Szeider, TU Wien
Date and Time:
Monday, August 15, 2016 - 2:30pm to 3:00pm
Location:
Bahen Building, Room 1200
Abstract:
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.