The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

Steffen Reith, Heribert Vollmer

We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns ou…