ECCC-Report TR98-022https://eccc.weizmann.ac.il/report/1998/022Comments and Revisions published for TR98-022en-usWed, 15 Apr 1998 03:07:38 +0300
Paper TR98-022
| The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae |
Steffen Reith,
Heribert Vollmer
https://eccc.weizmann.ac.il/report/1998/022We 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.
Wed, 15 Apr 1998 03:07:38 +0300https://eccc.weizmann.ac.il/report/1998/022