Abstract of Paper

Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems
by Steffen Reith and Heribert Vollmer

Abstract:

We consider the problems of finding the lexicographically minimal (or
maximal) satisfying assignment of propositional formulas for different
restricted classes of formulas. It turns out that for each class from our
framework, these problems are either polynomial time solvable or complete
for OptP. We also consider the problem of deciding if in the optimal
assignment the largest variable gets value 1. We show that this problem is
either in P or P to the NP complete.