The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

Details The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

1998-09-28

arxiv.org/abs/cs/9809116v1

Computer Science

Computational Complexity

17 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-481995