Parameterized Complexity of Weighted Satisfiability Problems
Heribert Vollmer ( University of Hannover, Germany )
- 16:30 22nd January 2013 ( week 2, Hilary Term 2013 )Lecture Theatre B
We consider the weighted satisfiability problem for Boolean circuits and propositional formulae, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and related counting problems and initiate a systematic study of the complexity of its fragments. "Systematic" here means that the fragments are defined in terms of Boolean operators taken from a clone in Post's lattice.