Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-022 | 14th April 1998 00:00

The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

RSS-Feed




TR98-022
Authors: Steffen Reith, Heribert Vollmer
Publication: 15th April 1998 03:07
Downloads: 3761
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint