TR98-022 Authors: Steffen Reith, Heribert Vollmer

Publication: 15th April 1998 03:07

Downloads: 2103

Keywords:

We consider the problems of finding the lexicographically

minimal (or maximal) satisfying assignment of propositional

formulae for different restricted formula classes. It turns

out that for each class from our framework, the above problem

is 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^NP complete.