Details
| Original language | English |
|---|---|
| Publication status | Published - 28 Sept 1998 |
Abstract
Keywords
- cs.CC, F.1.3
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
1998.
Research output: Working paper/Preprint › Technical report › Research
}
TY - UNPB
T1 - The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae
AU - Reith, Steffen
AU - Vollmer, Heribert
N1 - 17 pages, 1 figure
PY - 1998/9/28
Y1 - 1998/9/28
N2 - 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.
AB - 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.
KW - cs.CC
KW - F.1.3
M3 - Technical report
BT - The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae
ER -